数据结构——基础2
线性表：顺序表（数组）、链表（独立）
程序=算法+数据结构
数据结构=结构定义+结构操作
线性表的顺序存储又叫做顺序表，由一组地址连续的存储单元依次存储线性表中的数据元素，使逻辑上相邻的两个元素在物理位置上也相邻。
1、顺序表
结构定义：
#define MaxCnt 50//顺序表的最长长度
struct Sqlist{//顺序表的定义
EleType data[MaxCnt];//顺序表的数据
int len;//顺序表的长度
};
顺序表即可静态分配内存，又可以动态分配内存。动态分配时，需要将data变为指针。
顺序表的插入、删除、查找
#inlclude <stdlib.h>
typedef struct vector{
int *date;
int size,cap;//元素数量，容量上限
}vector;
//初始化顺序表
vector *init_vector(int x){
vector *p = (vector *)malloc(sizeof(vector));
p->data = (int *)malloc(sizeof(int)*x);
p->size = 0，p->cap = x;
return p;
}
void delete_vector(vector *p){
free(p->data);//防止内存泄露
free(p);
}
//在v中的ind位置插入元素x，先判插入位置是否合理，后将索引后面元素移位，再存插入元素
int insert_ele(vector *v, int ind, intx){
if(v->size < ind){//插入位置大于元素数量
return 1;//
}
if(v->size == v->cap){//元素数量与容量上限相同，已满扩容
v->cap *= 2;
v->data = (int *)realloc(v->data, sizeof(int) * v->cap);
}
for(int i = v->size - 1; i >= ind; i--){
v->data[i + 1] = v->data[i];
}
v->data[ind] = x;
v->size++;
return 0;
}
//v删除ind位置的元素,检查删除位置是否合法，
int delete_ele(vector *v,int ind){
if(v->size <= ind){//超过元素数量，元素不存在
return 1;
}
for(int i = ind + 1; i < v->size; i++){
v->data[i - 1] = v->data[i];
}
v->size--;
return 0;
}
void show_vector(vector *v){
printf("v->cap = %d, v->size = %d\n",v-cap, v->size);
for(int i = 0; i <v->size; i++){
printf("%d ", v->data[i]);
}
printf("--------------------------\n");
}
int main(){
int n,m;//操作数量 容量上限
scanf("%d%d",&n,&m);
vector *v = init_vector(m);//初始化
for(int i = 0; i < n; i++){
int t = 0;
scanf("%d", &t);//0表示插入，1表示删除
if(t == 0){
int ind,x;
scanf("%d%d", &ind, &x);
insert_ele(v, ind, x);
}
else{
int ind;
scanf("%d", &ind);
delete_ele(v, ind);
}
show_vectro(v);
}
delete_vector(v);
return 0;
}
运行结果：
2、单链表
顺序表的链式存储又叫做链表，在链表中每个元素的内存空间不连续，中间使用指针连接。
头结点之后存数据。
struct Node{//单链表的结点定义
EleType data;//结点的数据域
Node *next;//结点的指针域
};
struct list{//单链表的定义
Node *head;//单链表的头结点
int len;//单链表的长度
}；
通常用链表头结点指针与链表长度来表示一个单链表
typedef struct node{
int data;
struct node *next;
}node;
typedef struct list{
struct node *head;
int size;
}list;
//创建新结点
node *get_new_node(int x){
node *p = (node *)malloc(sizeof(node));
p->data = x;
p->next = null;
return p;
}
list *init_list(){
list *p = (list *)malloc(sizeof(list));
p->head = get_new_node(0);
p->size = 0;
return p;
}
//删除链表，从头结点开始删除，最后删除链表
void delete_list(list *p){
node *q = p->head;
while(q != NULL){
node *t = q;
q = q->next;
free(t);
}
free(p);
}
//l链表插入下标ind、元素x
int insert_ele(list *l, int ind, int x){
if(ind > l->size){//位置不对
return 1;
}
node *p = l->head;
for(int i = 0; i < ind; i++){//移动到插入位置
p = p->next;
}
node *t = get_new_node(x);//创建新结点
t->next = p->next;//先将新结点t的下一个元素指向p下一个元素
p->next = t;//后将p的下一元素指向新结点
l->size++;
return 0;
}
int delete_ele(list *l, int ind){
if(ind >= l->size){
return 1;
}
node *p = l->head;
for( int i = 0; i < ind; i++){
p = p->next;
}
node *t = p->next;//t为p的下一元素
p->next = t->next;//p的下一元素指向t的下一个元素
free(t);
l->size--;
return 0;
}
void show_list(list *l){
printf("l->size = %d", l->size);
for(node *p = l->head->next; p != NULL; p = p->next){//链表的遍历
printf("%d->",p->data);
}
printf("NULL\n------------------------------\n");
}
int main(){
int n;
sacnf("%d", &n);
list *l = init_list();
for(i = 0; i < n; i++){
int t;
scanf("%d", &t);
if (t == 0){//同上，约定第一个元素为0
int ind,x;
scanf("%d%d", ind, x);
insert_ele(l, ind, x);
}
else{
int ind;
scanf("%d", &ind);
delete_ele(ind);
}
show_list(l);
}
delete_list(l);
return 0;
}
运行结果：
总结：顺序表（地址连续）、单向链表（地址不连续）
