學(xué)習(xí)地址:http://blog.csdn.net/stpeace/article/details/8091123 #include<iostream>using namespace std;typedef struct LNode {int data;struct LNode *next; }LNode,*List;List createList()//創(chuàng)建鏈表 {LNode *head,*p1,*p2;p1=p2=head=new LNode;//分配內(nèi)存，head指的是頭結(jié)點，頭結(jié)點不存放數(shù)據(jù)int a;cin>>a;while(0!=a)//設(shè)置一個結(jié)束標(biāo)志用于創(chuàng)建鏈表{p1->data=a;p2->next=p1;//這時p2是一個新節(jié)點，p1又是下一個節(jié)點p2=p1;//把完成的節(jié)點賦給p2,使其成為一個節(jié)點p1=new LNode;cin>>a;}p2->next=NULL;return head; }int getLength(List p)//求鏈表的長度，不包括頭結(jié)點 {int length=0;while(NULL!=p->next){length++:p=p->next;//前移}return length; }//把元素elem插入到pos位置 List insert(List p,int pos,int elem)//向鏈表中插入元素 {int length=getLength(p);//求得長度if(pos<1||pos>length+1)//length不包括頭結(jié)點，length為1即表示第一個節(jié)點{cout<<"error"<<endl;exit(1);//退出}LNode *p1=p->next;//elem后的那個節(jié)點LNode *p1=p;//elem前的那個節(jié)點int i;for(i=0;i<pos-1;i++)//鏈表只能一個個找{p2=p1;//p2在前，p1在后p1=p1->next;}LNode *s=new LNode;s->data=elem;p2->next=s;s->next=p1;//調(diào)整指向return p; }List del(List p,int a)//刪除指定值所指的節(jié)點 {LNode *p1=NULL,p2=NULL;if(NULL==p->next){return p;//這里p是最后一個節(jié)點}p1=p1->next;//a的后一個節(jié)點p2=p;//a前一個節(jié)點，剛開始時也相當(dāng)于頭結(jié)點while(NULL!=p1&&a!=p1->data){p2=p1;p1=p1->next;//這兩段代碼實現(xiàn)了節(jié)點前移}if(NULL=p1)//表示已到最后一個節(jié)點{cout<<"not found"<<endl;}else{p2->mext=p1->next;delete p1;}return p; }void release(List p)//遞歸釋放鏈表 {if(NULL==p->next){delete p;}else{release(p->next);//釋放節(jié)點} }void Xrelease(List p) {List temp;//temp是指向一個結(jié)構(gòu)體數(shù)據(jù)的指針，p傳進來的是指向頭結(jié)點的指針while(p){temp=p;p=p->next;delete temp;//temp是一個指針,釋放p指向的那個地址} }void print(List p)//打印鏈表 {while(NULL!=p->next)//成立，p表示最后一個節(jié)點{cout<<p->next->data<<endl;p=p->next;} }//遞增歸并鏈表 void merge1(LNode *A,LNode *B,LNode *&C)//A,B,C都是頭結(jié)點 {LNode *p=A->next;//指向最小節(jié)點LNode *q=B->next;LNode *r;//r始終指向C的終端節(jié)點(每增加一個節(jié)點后的終端節(jié)點)C=A;//用A的頭結(jié)點做C的頭結(jié)點C->next=NULL;free(B);//用指針指向B的第一個有效節(jié)點，然后釋放頭結(jié)點r=C;while(p!=NULL&&q!=NULL){if(p->data<=q->data)//一個一個比較{r->next=p;p=p->next;r=r->next;}else{r->next=q;q=q->next;r=r->next;}}r->next=NULL;if(p!=NULL) r->next=p;//當(dāng)一個鏈表插入完成后，另一個鏈表補到后面if(q!=NULL) r->next=q; }//使用尾插法，用數(shù)組中的元素建立鏈表 List createListW(LNode *&C,int a[],int n) {LNode *s,*r;//s指向新申請的節(jié)點,r始終指向C的終端節(jié)點int i;C=new LNode;C->next=NULL;r=C;//r指向頭結(jié)點，此時頭結(jié)點就是終端節(jié)點for(i=0;i<n;i++){s=new LNode;s->data=a[i];r->next=s;r=r->next;}r->next=NULL;return C; }//利用數(shù)組元素，使用頭插法建立鏈表，頭插法從頭部開始插入，得到的鏈表的數(shù)據(jù)將是倒過來的 List createListT(LNode &*C,int a[],int n) {LNode *s;int i;C=new LNode;C->next=NULL;for(i=0;i<n;i++){s=new LNode;s->data=a[i];s->next=C->next;//s的指針域指向了C了，C->next為C的指針域C->next=s;}return C; }//頭插法實現(xiàn)遞減 List merge5(LNode *A,LNode *B,LNode *&C) {LNode *p=A->next;LNode *q=B->next;LNode *s;C=A;C->next=NULL;free(B);while(p!=NULL&&q!=NULL){if(p->data<=q->data){s=p;p=p->next;s->next=C->next;C->next=s;}else{s=q;q=q->next;s->next=C->next;C->next=s;}}while(q!=NULL){s=q;q=q->next;s->next=C->next;C->next=s;}while(p!=NULL){s=p;p=p->next;s->next=C->next;C->next=s;}return C; }int main() {List head;head=createList();print(head);int a; a=getLength(head);int b=3;insert(head,3,b);int c=5;del(head,3,b);List head3;List head1=createList();List head2=createList();merge1(head1,head2,head3);release(head);//Xrelease(head);List head4;int d[5]={1,2,3,4,5};createListW(head,d,5);List head5;int e[5]={4,5,6,7,8};createListT(head5,e,5);merge5(head1,head2,head3);return 0;}

那個createList的函數(shù)中，p1=new Node;這行代碼應(yīng)該在p1->data=a;這行代碼的上面。這樣頭結(jié)點才不會有數(shù)據(jù)。源代碼修改不方便，故在后面說一下

?

?

?

總結(jié)

以上是生活随笔為你收集整理的单链表建立(头插法，头插法，用数组)，求长，插入，删除，输出，释放（递归释放和循环释放），归并（递增和递减）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。