试编写在带头结点的单链表上实现线性表基本运算定位、查找、插入和删除的算法。
(1)定位 在带头结点的单链表上实现的算法为： int LocateLinklist(LinkList head，DataType x) ／／求表head中第一个值等于X的结点的序号，若不存在这种结点，返回结果为0 { Node*p=head； ／／P是工作指针 p=p一)next； ／／初始时P指向首结点 int i=0； ／／i代表结点的序号，这里置初值为0 while(p!=NULL＆＆p—>data!=x) ／／访问链表 {i+4-； P=P一>next； } if(p!=NULL) return i+1； else return 0； } (2)按序号查找 在带头结点的单链表上实现的算法为： Node*GetLinklist(LinkList head，int i) ／／在单链表head中查找第i个元素结点。若找到，则返回指向该结点的指针；否则返 ／／回N ULL { Node *p； ／／P是工作指针 p=head一>next； ／／初始时，P指向首结点 int c=1； while((cnext；c++；) if(i==c) return P； ／／找到第i个结点 else return NULL； ／／i<1或i>n，i值不合法，查找失败 } (3)插入 在带头结点的单链表上实现的算法为： void InsertLinklist(LinkList head，DataType X，int i) ／／在表head的第i个数据元素结点之前插入一个以X为值的新结点 { Node*p，*q； if(i==1)q=head； else q=GetLinklist(head，i一1)； ／／找第i一1个数据元素结点 if(q==NULL) ／／第i一1个结点不存在 exit("找不到插入的位置")； else { p=malloc(sizeof(Node))；p一>data=x；／／生成新结点 p m>next=q一>next； ／／新结点链域指向*q的后继结点 q一>next--P； ／／修改*q的链域 } } (4)删除 在带头结点的单链表上实现的算法为： void DeleteLinklist(LinkList head，int i) ／／删除表head的第i个结点 { Node*q； if(i==1)q=head； else q=GetLinklist(head，i一1)； ／／先找待删结点的直接前驱 if(q!==NULL＆＆q->next!=NULL) ／／若直接前驱存在且待删结点存在 { p=q一>next； ／／P指向待删结点 q一>next=p一>next； ／／移出待删结点 free(p)； ／／释放已移出结点P的空间 } else exit("找不到要删除的结点")； ／／结点不存在 }
