線性表的順序存儲(chǔ)結(jié)構(gòu)在查找指定位置的元素時(shí)操作較快猛拴，但是在插入和刪除操作的時(shí)候需要移動(dòng)大量數(shù)據(jù)的位置，操作較為耗時(shí)瞧柔，造成這種結(jié)果的原因在于順序存儲(chǔ)是開(kāi)辟一塊連續(xù)的內(nèi)存空間漆弄，各個(gè)數(shù)據(jù)之間緊緊相鄰；那么解決順序存儲(chǔ)插入和刪除問(wèn)題就需要采取另外一種存儲(chǔ)結(jié)構(gòu)--鏈?zhǔn)酱鎯?chǔ)造锅；
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
在順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素只要存儲(chǔ)數(shù)據(jù)元素信息就可以了撼唾，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)還需要存儲(chǔ)下一個(gè)結(jié)點(diǎn)的內(nèi)存地址，即每個(gè)數(shù)據(jù)元素成為一個(gè)獨(dú)立的結(jié)點(diǎn)哥蔚，結(jié)點(diǎn)包含數(shù)據(jù)信息和地址信息兩個(gè)部分倒谷；n個(gè)這樣的結(jié)點(diǎn)就構(gòu)成了鏈表，
單鏈表
因?yàn)榻Y(jié)點(diǎn)中只存在一個(gè)地址指針糙箍，即該鏈表又稱之為單鏈表
頭結(jié)點(diǎn)
排在單鏈表的第一個(gè)結(jié)點(diǎn)前的結(jié)點(diǎn)叫頭結(jié)點(diǎn)
頭指針
鏈表第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置即為頭指針/ 頭結(jié)點(diǎn)中存放的指針即為頭指針
單鏈表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
typedef int ElemType;
typedef struct Node{
ElemType data;
struct Node * next;
}Node;
typedef struct Node* LinkList;
一個(gè)結(jié)點(diǎn)的構(gòu)成包含數(shù)據(jù)域和指針區(qū)域渤愁；
單鏈表的初始化
LinkList linkListInit(){
Node* L ;
L = (Node*)malloc(sizeof(Node));
if (L == NULL) {
printf("申請(qǐng)內(nèi)存空間失敗\n");
}
L ->next = NULL;
return L;
}
創(chuàng)建單鏈表之頭插入方法
LinkList linkListCreateHeaderMethod(int numberOfNode){
Node* L ;
L = (Node*)malloc(sizeof(Node));
if (L==NULL) {
return NULL;
}
L->next = NULL;
for (int i =0; i<numberOfNode; i++) {
Node *p;
p =(Node*) malloc(sizeof(Node));
p -> data = i ;
p->next = L->next; //將結(jié)點(diǎn)插入到表頭L-->|3|-->|2|-->|1|-->NULL
L -> next = p;
}
return L;
}
頭插入法創(chuàng)建單鏈表是在頭指針和第一個(gè)結(jié)點(diǎn)之間完成插入操作，新節(jié)點(diǎn)的指針存放的是上一個(gè)作為第一個(gè)結(jié)點(diǎn)的地址即L->next深夯；然后再講L->next指向新節(jié)點(diǎn)p即可抖格；
創(chuàng)建單鏈表之尾插入方法
LinkList linkListCreateTailMethod(int numberOfNode){
Node* L ;
L = (Node*)malloc(sizeof(Node));
if (L==NULL) {
return NULL;
}
L -> next = NULL;
Node* tempL = L;
for (int i = 0; i<numberOfNode; i++) {
Node* p ;
p = (Node*)malloc(sizeof(Node));
p ->data = i ;
tempL -> next = p ;
tempL = p ;
}
tempL ->next = NULL;
return L;
}
尾插入就是將新建立的結(jié)點(diǎn)放在鏈表的最后；
單鏈表的插入操作
int linkListInsert(LinkList list ,int index,int e){
Node* pre ;
pre = list;
for (int i = 1; i<index; i++) {
pre = pre ->next;
}
if (pre) {
Node* newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = e ;
newNode->next = pre->next;
pre->next = newNode;
return 1;
}
return 0;
}
單鏈表的刪除操作
int linkListDeleteNode(LinkList list ,int e){
Node *p,*pre = NULL; //pre為前驅(qū)結(jié)點(diǎn)咕晋，p為查找的結(jié)點(diǎn)雹拄。
p = list->next;
while(p->data != e) //查找值為x的元素
{
pre = p;
p = p->next;
}
pre->next = p->next; //刪除操作，將其前驅(qū)next指向其后繼掌呜。
free(p);
return 1;
}
單鏈表返回指定位置的結(jié)點(diǎn)數(shù)據(jù)
int GetElem(LinkList list,int index,ElemType *e){
int i=1;
LinkList p ;
p = list ->next; // 默認(rèn)鏈表名作為第一個(gè)結(jié)點(diǎn)的指針
while (i<index&&p) {
p = p ->next;
i++;
}
if (!p||i>index) {
return 0;
}else{
*e = p->data;
return 1;
}
}
