这一章是单链表的算法分析和代码实现。
单链表的结点数据结构:
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<stdio.h>
#include<stdlib.h>
#include<iostream>
#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 < 1) //若i无效则返回NULL
return NULL;
while (p && j<i) //从第一个结点开始找,找到第i个结点
{ //在p == NULL(表遍历结束)或j == i(已找到第i个结点)时跳出循环
p = p->next;
j++;
}
return p; //返回第i个结点的指针,若i大于表长返回NULL
}
/*按值查找结点*/
LNode* LocateElem(LinkList L, ElemType e) {
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)
return false;
q = p->next; //q指向被删除结点
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;
}