c语言 链表操作:建立,显示及节点的插入,删除

Question

如题所述

Answer 1

先写个头文件，包含链表的各种操作。具体代码如下：
#ifndef LINKEDLIST_H_INCLUDED
#define LINKEDLIST_H_INCLUDED

//线性表的单链表存储结构
struct LNode
{
ElemType data;
LNode *next;
};
typedef LNode *LinkList; // 另一种定义LinkList的方法

//单链表线性表的基本操作(12个)
int InitList(LinkList &L)
{
// 操作结果：构造一个空的线性表L
L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
if(!L) // 存储分配失败
exit(0);
L->next=NULL; // 指针域为空
return 1;
}

void CreateList_L(LinkList &L, int n) // 算法2.11
{
// 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L
LinkList p;
int i;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; // 先建立一个带头结点的单链表
for (i=n; i>0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
p->data = rand()%200; // 改为一个随机生成的数字(200以内)
p->next = L->next;
L->next = p; // 插入到表头
}
} // CreateList_L

int DestroyList(LinkList &L)
{
// 初始条件：线性表L已存在。操作结果：销毁线性表L
LinkList q;
while(L)
{
q=L->next;
free(L);
L=q;
}
return 1;
}

int ClearList(LinkList L) // 不改变L
{
// 初始条件：线性表L已存在。操作结果：将L重置为空表
LinkList p,q;
p=L->next; // p指向第一个结点
while(p) // 没到表尾
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; // 头结点指针域为空
return 1;
}

int ListEmpty(LinkList L)
{
// 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if(L->next) // 非空
return 0;
else
return 1;
}

int ListLength(LinkList L)
{
// 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
int i=0;
LinkList p=L->next; // p指向第一个结点
while(p) // 没到表尾
{
i++;
p=p->next;
}
return i;
}

int GetElem(LinkList L,int i,ElemType &e) // 算法2.8
{
// L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回1,否则返回-1
int j=1; // j为计数器
LinkList p=L->next; // p指向第一个结点
while(p&&j<i) // 顺指针向后查找,直到p指向第i个元素或p为空
{
p=p->next;
j++;
}
if(!p||j>i) // 第i个元素不存在
return -1;
e=p->data; // 取第i个元素
return 1;
}

int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType))
{
// 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)
// 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在,则返回值为0
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(compare(p->data,e)) // 找到这样的数据元素
return i;
p=p->next;
}
return 0;
}

int PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
{
// 初始条件: 线性表L已存在
// 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,
// 返回1;否则操作失败,pre_e无定义,返回-1
LinkList q,p=L->next; // p指向第一个结点
while(p->next) // p所指结点有后继
{
q=p->next; // q为p的后继
if(q->data==cur_e)
{
pre_e=p->data;
return 1;
}
p=q; // p向后移
}
return -1;
}

int NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
{
// 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 返回1;否则操作失败，next_e无定义，返回-1
LinkList p=L->next; // p指向第一个结点
while(p->next) // p所指结点有后继
{
if(p->data==cur_e)
{
next_e=p->next->data;
return 1;
}
p=p->next;
}
return -1;
}

int ListInsert(LinkList L,int i,ElemType e) // 算法2.9。不改变L
{
// 在带头结点的单链线性表L中第i个位置之前插入元素e
int j=0;
LinkList p=L,s;
while(p&&j<i-1) // 寻找第i-1个结点
{
p=p->next;
j++;
}
if(!p||j>i-1) // i小于1或者大于表长
return -1;
s=(LinkList)malloc(sizeof(LNode)); // 生成新结点
s->data=e; // 插入L中
s->next=p->next;
p->next=s;
return 1;
}

int ListDelete(LinkList L,int i,ElemType &e) // 算法2.10。不改变L
{
// 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋
{
p=p->next;
j++;
}
if(!p->next||j>i-1) // 删除位置不合理
return -1;
q=p->next; // 删除并释放结点
p->next=q->next;
e=q->data;
free(q);
return 1;
}

int ListTraverse(LinkList L,void(*vi)(ElemType))
// vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同
{
// 初始条件：线性表L已存在
// 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
return 1;
}
LinkList ReverseList(LinkList phead)//实现链表的逆置
{
LinkList p,q,r;
p=phead;
q=r=NULL;
while(p)
{
q=p->next;
p->next=r;
r=p;
p=q;
}
return r;

}

#endif // LINKEDLIST_H_INCLUDED

再写主函数：
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
#include "LinkedList.h"

int compare(ElemType c1,ElemType c2)
{
if(c1==c2)
return 1;
else
return 0;
}

void visit(ElemType c)
{
printf("%d ",c);
}

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{
// 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
LinkList pa, pb, pc;
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的头结点
} // MergeList_L

int main()
{
LinkList L;
ElemType e,e0;
int i;

InitList(L);
for(i=1; i<=10; i++)
ListInsert(L,1,10-i);
//CreateList_L(L,10);
printf("在L的表尾依次插入10个数据后：L=");
ListTraverse(L,visit);

GetElem(L,4,e);
printf("第4个元素的值为：%d\n",e);

ListDelete(L,4,e); // 删除第4个数据
printf("删除第4个数据后：L=");
ListTraverse(L,visit);

DestroyList(L);

LinkList La, Lb, Lc;
int a[4] = {3,5,8,11};
int b[7] = {2,6,8,9,11,15,20};
InitList(La);
InitList(Lb);
for(i=1; i<=4; i++)
ListInsert(La, i, a[i-1]);
for(i=1; i<=7; i++)
ListInsert(Lb, i, b[i-1]);
printf("La=");
ListTraverse(La,visit);
printf("Lb=");
ListTraverse(Lb,visit);

MergeList_L(La, Lb, Lc);

printf("Lc=");
ListTraverse(Lc,visit);

DestroyList(Lc);
}
你不需要的操作可以注释掉！追问

真么办，求解

追答

这是两个文件，一个是头文件.h;
一个是cpp文件。你不能把两个文件直接放在一起，我用的是CodeBlocks，运行没有问题。