線性表：順序表（數(shù)組）、鏈表（獨(dú)立）

程序=算法+數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)=結(jié)構(gòu)定義+結(jié)構(gòu)操作

線性表的順序存儲(chǔ)又叫做順序表，由一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素，使邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰。

1、順序表

結(jié)構(gòu)定義：

#define?MaxCnt 50//順序表的最長(zhǎng)長(zhǎng)度

struct Sqlist{//順序表的定義

????EleType data[MaxCnt];//順序表的數(shù)據(jù)

????int len;//順序表的長(zhǎng)度

};

順序表即可靜態(tài)分配內(nèi)存，又可以動(dòng)態(tài)分配內(nèi)存。動(dòng)態(tài)分配時(shí)，需要將data變?yōu)橹羔槨?/p>

順序表的插入、刪除、查找

#inlclude <stdlib.h>

typedef struct vector{

????int *date;

????int size,cap;//元素?cái)?shù)量，容量上限

}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);//防止內(nèi)存泄露

????free(p);

}

//在v中的ind位置插入元素x，先判插入位置是否合理，后將索引后面元素移位，再存插入元素

int insert_ele(vector *v, int ind, intx){

????if(v->size < ind){//插入位置大于元素?cái)?shù)量

????????return 1;//

????}

????if(v->size == v->cap){//元素?cái)?shù)量與容量上限相同，已滿擴(kuò)容

????????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){//超過(guò)元素?cái)?shù)量，元素不存在

????????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;//操作數(shù)量?容量上限

????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;

}

運(yùn)行結(jié)果：

2、單鏈表

????順序表的鏈?zhǔn)酱鎯?chǔ)又叫做鏈表，在鏈表中每個(gè)元素的內(nèi)存空間不連續(xù)，中間使用指針連接。

????頭結(jié)點(diǎn)之后存數(shù)據(jù)。

struct Node{//單鏈表的結(jié)點(diǎn)定義

????EleType data;//結(jié)點(diǎn)的數(shù)據(jù)域

????Node *next;//結(jié)點(diǎn)的指針域

};

struct list{//單鏈表的定義

????Node *head;//單鏈表的頭結(jié)點(diǎn)

????int len;//單鏈表的長(zhǎng)度

}；

通常用鏈表頭結(jié)點(diǎn)指針與鏈表長(zhǎng)度來(lái)表示一個(gè)單鏈表

typedef struct?node{

????int data;

????struct node *next;

}node;?

typedef struct list{

????struct node *head;

????int size;

}list;

//創(chuàng)建新結(jié)點(diǎn)

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;

}

//刪除鏈表，從頭結(jié)點(diǎn)開(kāi)始刪除，最后刪除鏈表

void delete_list(list *p){

????node *q = p->head;

????while(q != NULL){

????????node *t = q;

????????q = q->next;

????????free(t);

????}

????free(p);

}

//l鏈表插入下標(biāo)ind、元素x

int insert_ele(list *l, int ind, int x){

????if(ind > l->size){//位置不對(duì)

????????return 1;

????}

????node *p = l->head;

????for(int i = 0; i < ind; i++){//移動(dòng)到插入位置

????????p = p->next;

????}

????node *t = get_new_node(x);//創(chuàng)建新結(jié)點(diǎn)

????t->next = p->next;//先將新結(jié)點(diǎn)t的下一個(gè)元素指向p下一個(gè)元素

????p->next = t;//后將p的下一元素指向新結(jié)點(diǎn)

????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的下一個(gè)元素

????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){//同上，約定第一個(gè)元素為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;

}

運(yùn)行結(jié)果：

總結(jié)：順序表（地址連續(xù)）、單向鏈表（地址不連續(xù)）