|
这一章是单链表的算法分析和代码实现。
单链表的结点数据结构：
typedef struct LNode {
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, *LinkList ;
主要有以下实现功能的函数：
LinkList List_HeadInsert(LinkList& L) 功能：头插法建立单链表（逆向建立单链表）； 参数：L:链表； 时间复杂度：O(n); LinkList List_TailInsert(LinkList& L) 功能：尾插法建立单链表（正向建立单链表）； 参数：L:链表； 时间复杂度：O(n)； LNode* GetElem(LinkList L, int i) 功能：按序号查找结点； 参数：L:链表 , i:要查找的结点的位置; 时间复杂度：O(n); LNode* LocateElem(LinkList L, ElemType e) 功能：按值查找结点（查找第一次出现的）； 参数：L:链表，e:要查找的结点的值； 时间复杂度：O(n)； bool LNodeInsert(LinkList &L,int i,ElemType e) 功能：插入一个结点； 参数：L:链表 ，i:插入的位置，e:插入结点的值 时间复杂度：O(n); bool LNodeDelete(LinkList &L, int i) 功能：删除一个结点； 参数：L:链表，i:删除结点的位置； 时间复杂度：O(n); bool LNodeRevise(LinkList& L, int i, ElemType e) 功能：修改一个结点的值； 参数：L:链表，i:要修改的结点位置，e:要改成的值； 时间复杂度：O(n)； int LinkLength(LinkList L) 功能：求表长； 参数：L:链表； 时间复杂度：O(n)； void PrintList(LinkList L) 功能：输出所有结点的值； 参数：L:链表； 时间复杂度：O(n);
可能理解困难的地方： 关于头插法和尾插法：头插法是把每次插入的结点都放到头结点后一位；而尾插法有尾结点指针，每次插入新结点到尾结点后面，然后把尾结点指针移到新插入的结点上。所以用头插法建立的链表和输入的顺序倒序，而尾插法是顺序的。    完整代码：
#include
#include
#include
#define ElemType int
/*--------------------------------------------数据结构部分--------------------------------------------*/
/*单链表的数据结构*/
typedef struct LNode {
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, *LinkList ;
/*初始化链表*/
void InitList(LinkList& L) {
L = (LinkList)malloc(sizeof(LNode)); //创建头结点
L->next = NULL; //初始为空链表
}
/*头插法建立单链表（逆向建立单链表）*/
LinkList List_HeadInsert(LinkList& L) {
LNode* s,* p; //s是创建的结点的指针
int x;
InitList(L); //初始化链表
p = L;
scanf("%d", &x); //输入结点的值
while (x!=9999) //输入9999结束
{
s = (LNode*)malloc(sizeof(LNode)); //创建新结点
//s = new LNode //c++可以new
s->data = x;
s->next = p->next; //将新结点插入表中，s->next指向头结点外的第一个结点
p->next = s;
scanf("%d", &x);
}
return L;
}
/*尾插法建立单链表（正向建立单链表）*/
LinkList List_TailInsert(LinkList& L) {
int x;
InitList(L);
LNode* s, * r = L; //r为表尾指针
scanf("%d", &x);
while (x!=9999)
{
s = new LNode;
s->data = x;
r->next = s; //把新结点s添加到表尾r
r = s; //r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL; //尾结点指针置空
return L;
}
/*按序号查找结点*/
LNode* GetElem(LinkList L, int i) {
int j = 1; //计数，初始为1
LNode* p = L->next; //头结点赋值给p
if (i == 0) //若i == 0 则返回头结点
return L;
if (i
LNode* p = L->next;
while (p != NULL && p->data != e) //从第1个结点开始查找data为e的结点
{
p = p->next; //移动结点指针
}
return p; //找到后返回该节点的指针，否则返回NULL
}
/*插入结点*/
bool LNodeInsert(LinkList &L,int i,ElemType e) {
LNode* s;
LinkList p = L;
p = GetElem(L, i - 1); //查找插入位置的前驱结点
if (!p)
return false;
s = new LNode;
s->data = e;
s->next = p->next; //s->next指向原来p的下一个结点
p->next = s; //p->next指向新增的s结点
return true;
}
/*删除结点*/
bool LNodeDelete(LinkList &L, int i) {
LNode* q;
LinkList p = L;
p = GetElem(L, i - 1); //查找删除位置的前驱结点
if (!p) //未找到第i个位置的前驱结点，返回false
return false;
q = p->next; //q指向被删除结点
if (!q) //边界判断：第i个位置有前驱结点，但是不存在第i个位置的结点，返回false
return false;
p->next = q->next; //将*q结点从链中断开
free(q); //释放结点的存储空间
return true;
}
/*求表长*/
int LinkLength(LinkList L) {
LNode* p = L->next; //头节点不存放数据，不算长度
int sum = 0;
while (p)
{
p = p->next; //移动结点指针
sum++;
}
return sum; //返回表长
}
/*修改节点*/
bool LNodeRevise(LinkList& L, int i, ElemType e) {
LinkList p = L;
p = GetElem(L, i); //拿到要修改的结点
if (!p || i == 0) //结点不能为空，不能修改头结点
return false;
p->data = e; //修改结点的值
return true;
}
/*--------------------------------------------下面是功能函数--------------------------------------------*/
/*插入结点的功能*/
void Insert(LinkList& L) {
int location;
ElemType elem;
printf("输入要插入的元素：");
scanf("%d", &elem);
printf("要插入的位置：");
scanf("%d", &location);
if (LNodeInsert(L, location, elem))
printf("插入成功\n");
else
printf("插入失败\n");
}
/*删除结点的功能*/
void Delete(LinkList& L) {
int location;
printf("输入要删除的元素的位置：");
scanf("%d", &location);
if (LNodeDelete(L, location))
printf("删除成功\n");
else
printf("删除失败\n");
}
/*修改结点的功能*/
void Revise(LinkList& L) {
int i;
ElemType e;
printf("输入要修改的位置：");
scanf("%d", &i);
printf("修改为：");
scanf("%d", &e);
if (LNodeRevise(L, i, e))
printf("修改成功\n");
else
printf("修改失败\n");
}
void Search(LinkList L) {
int searchChoice;
printf("（1）按位查找\n");
printf("（2）按值查找\n");
printf("选择查找功能：\n");
scanf("%d", &searchChoice);
int i;
ElemType e;
LNode* p;
switch (searchChoice)
{
case(1):
printf("输入要查找的节点位置：");
scanf("%d", &i);
p = GetElem(L, i);
if (p && i != 0) //查找的结点不能为空，也不能查找头结点的值
printf("第%d个结点的值为%d\n", i, p->data);
else
printf("查找失败\n");
break;
case(2):
printf("输入要查找的结点的值：");
scanf("%d", &e);
p = LocateElem(L, e);
if (p)
printf("找到该元素,查找成功\n");
else
printf("找不到该元素,查找失败\n");
break;
default:
break;
}
}
void PrintList(LinkList L) {
LinkList p = L->next; //头结点无数据不输出
if (!p)
printf("表空\n");
else {
printf("链表数据：\n");
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n共%d个元素\n", LinkLength(L));
}
}
void menu() {
printf("\n\n");
printf("----------①前插法建立链表----------\n");
printf("----------②后插法建立链表----------\n");
printf("----------③ 插入结点 ----------\n");
printf("----------④ 删除结点 ----------\n");
printf("----------⑤ 修改结点 ----------\n");
printf("----------⑥ 查找结点 ----------\n");
printf("----------⑦ 打印表 ----------\n");
printf("按“0”退出\n");
printf("\n\n");
}
int main() {
LinkList L;
int choice;
do
{
menu();
scanf("%d", &choice);
switch (choice)
{
case(1):
printf("输入每个元素的值（输入9999停止建表）\n");
List_HeadInsert(L);
break;
case(2):
printf("输入每个元素的值（输入9999停止建表）\n");
List_TailInsert(L);
break;
case(3):
Insert(L);
break;
case(4):
Delete(L);
break;
case(5):
Revise(L);
break;
case(6):
Search(L);
break;
case(7):
PrintList(L);
break;
default:
break;
}
} while (choice!=0);
return 0;
}
|