线性表的链式表示和实现线性表的顺序表示是指用一组地址连续的存储单元依次存放线性表的数据元素以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑相邻线性表的顺序表示线性表的链式表示线性表的链式表示单链表单链表typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;LinkListL;//L为单链表的头指针带头结点的单链表带头结点的单链表单链表的遍历p=L->next;j=1;//可替换为：p=L;j=0;while(p!=NULL&&j<i){p=p->next;j++;}if(p!=NULL)对第i个结点操作；else第i个结点不存在；voidListInit_L(LinkList&L)//构造一个空链表{L=(LinkList)malloc(sizeof(LNode));L->next=NULL;}StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的单链表的头指针，以e返回第i个结点的值//确定第i个结点的位置p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)//第i个结点不存在returnERROR;e=p->data;//取得第i个结点的值returnOK;}算法时间复杂度为:O(ListLength(L))成正比StatusListInsert_L(LinkList&L,inti,ElemTypee){//L是带头结点的单链表的头指针，在第i个结点之前插入元素e//确定第i-1个结点的位置p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;//先连后！p->next=s;//再改前！returnOK;}StatusListDelete_L(LinkList&L,inti,ElemType&e){//L是带头结点的单链表的头指针，删除第i个结点，并用e返回其值//确定第i-1个结点的位置p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;q=p->next;//q指向第i个结点p->next=q->next;e=q->data;free(q);returnOK;}voidCreateList_L(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表//先建立一个带头结点的单链表L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//分配空间scanf(&p->data);//输入元素值p->next=L->next;L->next=p;//插入L之后!}}算法的时间复杂度为:O(Listlength(L))voidClearList(&L){//将单链表重新置为一个空表while(L->next){p=L->next;L->next=p->next;free(p);}}销毁Destory头结点也要释放掉算法时间复杂度：O(ListLength(L))voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//单链表La、Lb的结点按值非递减排列，归并La和Lb得到新链表Lc，且Lc的结点按值非递减排列。pa=La->next;pb=Lb->next;Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;//插入剩余段free(Lb);//释放Lb的头结点}特点：最后一个结点的指针域指向头结点