第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
单链表及其应用.docx
实验 单链表及其应用
【实验目的】
深入了解单链表的存储结构。
熟练掌握在单链表存储结构上进行插入、删除等操作的算法。
通过单链表结构解决现实中的一些问题。
通过本次实习帮助学生加深对高级语言 C 语言的使用（特别是函数参数、
指针类型、链表的使用）。
【实验内容】
1） 利用单链表实现电话本的模拟程序：定义单链表的数据类型，将头插法
和尾插法、插入、删除、查找、修改、计数、逆置、输出等操作都定义成子函
数的形式，最后在主函数中调用它，并将每一种操作前后的结果输出，以查看
每一种操作的效果。
2） 选作实验：
试设计一元多项式相加（链式存储）的加法运算。
A（X）=7+3X+9X8+5X9
B（X）=8X+22X7-9X8
（1）建立一元多项式；
（2）输出相应的一元多项式；
（3）相加操作的实现。
【程序源代码】
#include
#include
#include
#define flag -1
typedef char DataType;
typedef struct student{
DataType num[12];
DataType name[20];
struct student *next;
}LNode,*LinkList;
LinkList init(LinkList L);
LinkList TailCreate(LinkList L);
LinkList HeadCreate(LinkList L);
LNode *GetLinkList(LinkList L,DataType i);
1
LNode *LocationLinkList(LinkList L);
void InsertLinkList(LinkList L);
void DeleteLinkList(LinkList L);
void ModifyLinkList(LinkList L);
void FindLinkList(LinkList L);
void PrintLinkList(LinkList L);
void Reverse(LinkList L);
int main()
{
int n,m;
LinkList L = init(L);
while(1)
{
printf("\n\n\n\n
phonetxt-------------------\n\n");
|\n");
|\n");
|\n");
|\n");
|\n");
|\n");
|\n");
|\n");
|\n");
printf("
printf("
printf("
printf("
printf("
printf("
printf("
printf("
printf("
printf("\n\n\n\n
scanf("%d",&n);
switch(n){
---------------
Ansel's
|You could chose these options:
|
1.Create the phonetxt
|
|
|
2.Insert the member in the phonetxt
3.Delete the member in the phonetxt
4.Modify the member in the phonetxt
|
5.Reverse the member in the phonetxt
|
6.Find the member in the phonetxt
|
|
7.Print the phonetxt
8.Close the phonetxt
Now,you can enter an optiton:");
case 1:printf("
Which one of way you will
select:1.HeadCreate 2.TailCreate
: ");
if(scanf("%d",&m)==1)
TailCreate(L);
else
HeadCreate(L);
break;
2
case 2:InsertLinkList(L);
break;
case 3:DeleteLinkList(L);
break;
case 4:ModifyLinkList(L);
break;
case 5:Reverse(L);
break;
case 6:FindLinkList(L);
break;
case 7:PrintLinkList(L);
break;
case 8:exit(0);
};
}
return 0;
}
LinkList init(LinkList L)
{
LNode *news;
news=(LNode*)malloc(sizeof(LNode));
news->next=NULL;
return news;
}
void Reverse(LinkList L)
{
LNode *p,*q;
p=L->next;
L->next=NULL;
while(p){
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
PrintLinkList(L);
}
LinkList HeadCreate(LinkList L){
LNode *head,*p;
int n,i;
printf("
scanf("%d",&n);
How many members do you want to built: ");
3
for(i = 0;i < n ; i++)
{
p = (LinkList)malloc(sizeof(LNode));
printf("
scanf("%s",p->num);
printf("
scanf("%s",p->name);
Please input the name: ");
Please input the phone number: ");
p->next = L->next;
L->next = p ;
}
system("cls");
return L;
}
LinkList TailCreate(LinkList L)
{
LNode *r,*s;
int i;
r = L;
printf("
scanf("%d",&i);
if(L->next != NULL)
{
printf("
exit(0);
}
while(i)
{
How many members do you want to built: ");
电话本已经创建");
Please input the name: ");
s = (LinkList)malloc(sizeof(LNode));
printf("
scanf("%s",s->name);
printf("
scanf("%s",s->num);
r->next = s;
r = s;
i--;
Please input the phone number: ");
}
r->next = NULL;
system("cls");
return L;
}
LNode *GetLinkList(LinkList L,DataType i)
4
{
LNode *p;
int j;
p = L;
j = 0;
while(p!=NULL&&j < i )
{
p = p->next;
j++;
}
return p;
}
LNode *LocationLinkList(LinkList L)
{
LNode *p;
DataType name[20];
printf("
scanf("%s",name);
p = L->next;
while(p!=NULL&&p->name!=name)
{
Please the member you wannt to check: ");
p = p->next;
}
return p;
}
void InsertLinkList(LinkList L)
{
LNode *p,*s;
int i;
printf("
scanf("%d",&i);
p = GetLinkList(L,i-1);
if(p == NULL)
{
Please input the number you insert:");
printf("插入位置不合法");
exit(1);
}
else
{
s = (LinkList)malloc(sizeof(LNode));
printf("
scanf("%s",s->name);
printf("
scanf("%s",s->num);
Please input the inserted name: ");
Please input the inserted phone number: ");
5
s->next = p->next;
p->next = s;
}
system("cls");
}
void DeleteLinkList(LinkList L)
{
LNode *p,*q;
int i;
printf("
");
Please input member you would delete of number:
scanf("%d",&i);
p = GetLinkList(L,i-1);
if(p == NULL)
{
printf("删除的位置不合法！");
exit(1);
}
else
{
if(p->next == NULL)
{
printf("删除位置不合法！");
exit(1);
}
else
{
q = p->next;
p->next = p->next->next;
free(q);
}
}
system("cls");
}
void ModifyLinkList(LinkList L)
{
LNode *p;
int n;
p = L;
if(p == NULL)
{
printf("修改的位置不合法！");
exit(1);
}
6
else{
printf("
scanf("%d",&n);
for(int i=1;inext;
}
printf("
scanf("%s",p->name);
printf("
scanf("%s",p->num);
Please input the modefied name: ");
Please input the modefied phone number: ");
}
printf("\n
if(getchar() == 'Y') exit(0);
else {
Do you close the phonetxt?Y/N: ",getchar());
system("cls");
}
}
void FindLinkList(LinkList L)
{
LNode *p;
int i;
printf("
");
Please input member you would find of number:
scanf("%d",&i);
p = GetLinkList(L,i);
printf("
printf("\n
Please input the found name: %s",p->name);
Please
input
the
found
phone
number: %s",p->num);
Do you close the phonetxt?Y/N: ",getchar());
printf("\n
if(getchar() == 'Y') exit(0);
else {
system("cls");
}
}
void PrintLinkList(LinkList L)
{
LNode *p;
int i = 0;
p = L;
if(p->next==NULL)
{
printf("
当前没有联系人！\n");
}
while(p->next!=NULL)
7
{
p = p->next;
i++;
printf("
printf("
The %dth member's name: %s \n",i,p->name);
The %dth member's number: %s \n",i,p->num);
}
printf("\n
if(getchar() == 'Y') exit(0);
else {
Do you close the phonetxt?Y/N: ",getchar());
system("cls");
}
}
【算法分析】
LinkList HeadCreate(LinkList L);
头插法：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(n);
LinkList TailCreat(LinkList L);
尾插法：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(n);
LNode *Find(LinkList L);
查找：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(1);
void ModifyLinkList(LinkList L);
修改：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(1);
void ReverseLinkList(LinkList L);
倒置：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(1);
void InsertLinkList(LinkList L);
插入：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(1);
void DeleteLinkList(LinkList L);
删除：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(1);
void PrintLinkList(LinkList L);
输出：时间复杂度 T(n) = O(n);空间复杂度 S(n) = O(1);
【运行结果分析】
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
