带头结点的单链表的创建

带头结点的单链表的创建、求表长、输出、插入、删除、查找、逆置

//说明在VC6.0中不能把本代码保存为.c进行编译，应保存为.cpp，原因可能是里边注释是c++的风格，在codeblocks中不存在这个问题 #include #include #define DataType int #define FLAG -1 typedef struct Node {

DataType data; struct Node *next; }Lnode,*LinkList; LinkList Creat_LinkList() {

LinkList L; Lnode *s,*r; int x;

printf(\建立有表头结点的单链表，以%d作为创建链表完成的标志\\n\ L=r=s=NULL;

L=(Lnode *)malloc(sizeof(Lnode)); if(!L) {

printf(\表头结点开辟失败\\n\ exit(-1); }

L->next=NULL; scanf(\ while(x!=FLAG) {

s=(Lnode *)malloc(sizeof(Lnode)); if(!s) {

printf(\结点开辟失败\\n\ exit(-1); }

s->data=x;

if(NULL==L->next)//第一个结点的处理 L->next=s; else r->next=s; r=s;

scanf(\ }

if(r!=NULL)//对于非空表，最后结点的指针域放空指针 r->next=NULL; return L; }

/*有头结点的链表，求表长算法*/ int Length_LinkList(LinkList L) { Lnode *p; int j; p=L; j=0;

while(p->next) {

p=p->next; j++; } return j; }

int Print_LinkList(LinkList L) {

printf(\输出：\\n\ Lnode *s; s=L;

while(s->next!=NULL) {

s=s->next;

printf(\

}

printf(\ return 0; }

/*逆置算法思路：

依次取原链表中每个结点，将其作为第一个结点插入到新的 链表中去。指针p用来指向原表中当前结点，p为空时结束。*/ void Reverse_LinkList(LinkList H)//单链表的逆置 {

Lnode *p,*q;

p=H->next;//p指向第一个结点 H->next=NULL;//将原链表置为空表 while(p) { q=p; p=p->next;

q->next=H->next;//将当前节点插入到头结点后面 H->next=q; } return; }

/*按序号查找*/

Lnode *Get_LinkList(LinkList L,int i) {

Lnode *p; int j=0; p=L;

while(p->next!=NULL&&j

p=p->next; j++; } if(j==i) return p; else

return NULL; }

/*按值查找*/

Lnode *Locate_LinkList(LinkList L,DataType x) {

Lnode *p; p=L->next;

while(p!=NULL&&p->data!=x) p=p->next; return p; }

/*插入操作，分为：前插接点、后插结点.下面的算法实现在链表的第i个位置上插入一个数值 后插结点：设p指向单链表中某结点，s指向待插入值为x的新结点，将*s插入到*p之后， 操作：s->next=p->next;p->next=s;

前插接点：遇红茶结点不同德是，这种算法要先找到前驱结点*q，然后完成在*q后插入*s, 操作：q=L;while(q->next!=p)q=p->next;s->next=q->next;q->next=s;*/ int Insert_LinkList(LinkList L,int i,DataType x) {

Lnode *p,*s;

p=Get_LinkList(L,i-1); if(NULL==p) {

printf(\前驱结点不存在，不能插入\\n\ return 0; } else {

s=(Lnode *)malloc(sizeof(Lnode)); s->data=x; s->next=p->next; p->next=s; return 1; } }