1.单链表查找
Status GetElem_L(LinkList L,int i,ElemType &e) { //L是带头结点的单链表的头指针 p=L->next; //初始化，p指向第一个结点 j=1; //j为计数器 while(p&&j<i) { p=p->next; ++j; } if(!p||j>i) return ERROR; //返回错误 e=p->data; //取第i个元素 return OK; }
2.向单链表中插入一个数据
Status ListInsert_L(LinkList &L,int i ,ElemType e) { //在带头结点的单链线性表中第i个位置之前插入元素e p=L; j=0; while(p&&j<i-1) //寻找第i-1个结点，此时p指向第i-1个结点 { p=p->next; ++j; } if(!p||j>i) return ERROR; //返回错误 s=(LinkList)malloc(sizeof(LNode)); //分配内存，生成新的结点 s->data=e; //结点s的数据域为e s->next=p->next; //把结点s的指针域指向第i个结点（新的第i+1个结点），此时结点s变成新的第i个结点 p->next=s; //第i-1个结点的指针域指向第i个结点，即结点s return OK; }
//注释：头结点，在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。头结点的作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入、删除操作一致。
3.单链表中删除一个元素
Status ListDelete_L(LinkList &L ,int i,ElemType &e) { //带头结点的单链表L中，删除第i个元素，并由e返回其值 p=L; j=0; while(p->next&&j<i-1) { p=p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; q=p->next; //q指向第i个元素 p->next=q->next;//第i-1个元素指针域指向第i+1个元素 e=q->data; //e等于第i个元素的数据域 free(q); //释放； return OK; }
注：在为第i个结点增加或者删除一个结点之前，必须先找到第i-1个结点，即需修改指针的结点
4.从表尾到表头建立单链表的算法
void CreateList_L(LinkList &了，int n) { L=(LinkList)malloc(sizeof(LNode));//产生头结点 L->next=NULL; //头结点指向NULL for (int i = n; i >0; i--) { p=(LinkList)malloc(sizeof(LNode));//分配新的结点 scanf(&p->data); //输入新的结点的数据域 p->next=L->next; //第i个新结点的指针域指向第i-1个结点 L->next=p; //L的指针域指向第i个新结点 } }
5.合并两个有序的链表
void MergeList_L(LinkList & La,LinkList & Lb,LinkList & Lc) { pa=La->next; pb=Lb->next; Lc=pc=La; while(pa&&pb)//pc指向Lc当前最末尾的元素 { //pa，pb指向当前La，Lb最前端的元素 if(pa->data<=pb->data) { pc->next=pa; pc=pa; //即pc->next即为当前pa->next，使得pc指向Lc当前最末尾的元素 pa=pa->next;//pa指向La的下一个元素 } else { pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放Lb的头结点 }
6.静态链表，一维数组space中建立(A-B)U(B-A)
void difference(SLinkList & space,int & S) { InitSpace_SL(space); //初始化备用空间 S=Malloc_SL(space); //生成S的头结点 r=S; //r指向S的当前最后结点 scanf(m,n); //输入A和B的元素个数 for(j=1;j<=m;++j) { i=Malloc_SL(space); //分配结点 scanf(space[i].data);//输入A的元素值 space[r].cur=i; r=i; //插入到表尾 }//for space[r].cur=0; //尾结点的指针为空 for(j=1;j<=n;++j) //创建静态链表B { //依次输入B的元素，若不在当前表，则插入，否则删除 scanf(b); p=S; k=space[S].cur; //k指向集合A中第一个结点 while(k!=space[r].cur&&space[k].data!=b)//判断：k没有指向S中的最末尾元素 { //且k所指向元素的数据域不等于当前输入值b //在当前表中查找 p=k; k=space[k].cur; //k指向下一元素 }//while if(k==space[r].cur)//当前表中不存在该元素，插入在r所指结点后，且r的位置不变 { //即没有找到A中有与b相同的元素 i=Malloc_SL(space); //分配新结点 space[i].data=b; space[i].cur=space[r].cur;//space[i].cur指针为空，即 0 space[r].cur=i; //space[r].cur指向元素i }//if else //若该元素已在表中 { space[p].cur=space[k].cur; Free_SL(space,k); if(r==k) r=p; //若删除的是r所指结点，则需修改尾指针 }//else }//for }//difference
7.双向链表
typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; } NuLNode,*DuLinkList;
8.双向链表中插入元素
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e) { //在带头结点的双链循环线性表L中第i个位置之前插入元素e //i的合法值为1<=i<=表长+1 if(!(p=GetElemP_DuL(L,i))) //在L中确定插入位置 return ERROR; //p=NULL,即插入位置不合法 if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; //分配内存失败,返回错误 s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; //建立双向关系 return OK; }
9.双向链表中删减元素
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e) { //删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长 if(!(p=GetElemPDuL(L,i))) return ERROR; e=p->data; p->prior->next=p->next; p->next->prior=p->prior; free(p); return OK; }