数据结构与算法——实验一
链表
题目要求
实验题目：单链表的基本操作
实验目的：
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。
实验要求：
建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。
实验主要步骤：
1、 分析、理解给出的示例程序。
2、 调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。
3、 修改程序：
（1） 增加插入结点的功能。
（2） 增加建立链表的尾插入法。初始代码
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"ctype.h"
typedef struct node //定义结点
{
char data[10]; //结点的数据域为字符串
struct node *next; //结点的指针域
}ListNode;
typedef ListNode * LinkList; // 自定义LinkList单链表类型
LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表
LinkList CreatList(); //函数，用头插入法建立带头结点的单链表
ListNode *LocateNode(); //函数，按值查找结点
void DeleteList(); //函数，删除指定值的结点
void printlist(); //函数，打印链表中的所有值
void DeleteAll(); //函数，删除所有结点，释放内存
ListNode * AddNode(); //修改程序：增加节点。用头插法，返回头指针
//==========主函数==============
void main()
{
char ch[10],num[5];
LinkList head;
head=CreatList(); //用头插入法建立单链表，返回头指针
printlist(head); //遍历链表输出其值
printf(" Delete node (y/n):"); //输入"y"或"n"去选择是否删除结点
scanf("%s",num);
if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){
printf("Please input Delete_data:");
scanf("%s",ch); //输入要删除的字符串
DeleteList(head,ch);
printlist(head);
}
printf(" Add node ? (y/n):"); //输入"y"或"n"去选择是否增加结点
scanf("%s",num);
if(strcmp(num,"y")==0 || strcmp(num,"Y")==0)
{
head=AddNode(head);
}
printlist(head);
DeleteAll(head); //删除所有结点，释放内存
}
//==========用尾插入法建立带头结点的单链表===========
LinkList CreatListR1(void)
{
}
//==========用头插入法建立带头结点的单链表===========
LinkList CreatList(void)
{
while(1)
{
printf("Input # to end ");
printf("Please input Node_data:");
scanf("%s",ch);
if(strcmp(ch,"#"))
{
if(LocateNode(head,ch)==NULL)
{
}
}
else
break;
}
return head;
}
//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode *LocateNode(LinkList head, char *key)
{
}
//==========增加节点=======
ListNode * AddNode(LinkList head)
{
}
//==========删除带头结点的单链表中的指定结点=======
void DeleteList(LinkList head,char *key)
{
ListNode *p,*r,*q=head;
p=LocateNode(head,key); //按key值查找结点的
if(p==NULL ) { //若没有找到结点，退出
printf("position error");
exit(0);
}
}
//===========打印链表=======
void printlist(LinkList head)
{
ListNode *p=head->next; //从开始结点打印
while(p){
printf("%s, ",p->data);
p=p->next;
}
printf("\n");
}
//==========删除所有结点，释放空间===========
void DeleteAll(LinkList head)
{
ListNode *p=head,*r;
}
代码实现
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"ctype.h"
typedef struct node //定义结点
{
char data[10]; //结点的数据域为字符串
struct node *next; //结点的指针域
}ListNode;
typedef ListNode * LinkList; // 自定义LinkList单链表类型
LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表
LinkList CreatList(); //函数，用头插入法建立带头结点的单链表
ListNode *LocateNode(); //函数，按值查找结点
void DeleteList(); //函数，删除指定值的结点
void printlist(); //函数，打印链表中的所有值
void DeleteAll(); //函数，删除所有结点，释放内存
ListNode * AddNode(); //修改程序：增加节点。用头插法，返回头指针
//==========主函数==============
int main()
{
char ch[10],num[5];
LinkList head;
head=CreatListR1(); //用头插入法建立单链表，返回头指针 这里可以切换尝试头插法和尾插法
printlist(head); //遍历链表输出其值
printf(" Delete node (y/n):"); //输入"y"或"n"去选择是否删除结点
scanf("%s",num);
if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){
printf("Please input Delete_data:");
scanf("%s",ch); //输入要删除的字符串
DeleteList(head,ch);
printlist(head);
}
printf(" Add node ? (y/n):"); //输入"y"或"n"去选择是否增加结点
scanf("%s",num);
if(strcmp(num,"y")==0 || strcmp(num,"Y")==0)
{
head=AddNode(head);
printlist(head);
}
DeleteAll(head); //删除所有结点，释放内存
return 1;
}
//==========用尾插入法建立带头结点的单链表===========
LinkList CreatListR1(void)
{
LinkList head;
head = (LinkList)malloc(sizeof(LinkList));
head->next = NULL;
ListNode *p, *q = head; // 创建新增节点p和尾指针q
while(1)
{
printf("Input # to end ");
printf("Please input Node_data:");
char ch[10];
scanf("%s",ch);
if(strcmp(ch,"#"))
{
if(LocateNode(head,ch)==NULL)
{
p = (ListNode *)malloc(sizeof(ListNode));
strcpy(p->data, ch);
p->next = NULL; // 这一步真重要，之前一直卡在这里，若没赋空值，赋给p后，进入LocateNode判断会报错，因为q->next->next不是个地址同时也不为空！
q->next = p;
q = p;
// p->next = NULL;
}
}
else
break;
}
q->next = NULL;
return head;
}
//==========用头插入法建立带头结点的单链表===========
LinkList CreatList(void)
{
LinkList head;
head = (ListNode *)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *p = NULL;
while(1)
{
printf("Input # to end ");
printf("Please input Node_data:");
char ch[10];
scanf("%s", ch);
if(strcmp(ch,"#"))
{
if(LocateNode(head,ch)==NULL)
{
p = (ListNode *)malloc(sizeof(ListNode));
strcpy(p->data, ch);
p->next = head->next;
head->next = p;
}
else
printf("You have already input this Node_data!\n");
}
else
{
break;
}
}
return head;
}
//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode *LocateNode(LinkList head, char *key)
{
ListNode *p = head->next;
while (p && strcmp(p->data,key))
{
p = p->next;
}
return p;
}
//==========增加节点=======
ListNode * AddNode(LinkList head)
{
ListNode *p = head->next;
printf("Please input Node_data:");
char ch[10];
scanf("%s", ch);
if(LocateNode(head,ch)==NULL)
{
p = (ListNode *)malloc(sizeof(ListNode));
strcpy(p->data, ch);
p->next = head->next;
head->next = p;
}
else
printf("You have already input this Node_data!\n");
return head;
}
//==========删除带头结点的单链表中的指定结点=======
void DeleteList(LinkList head, char *key)
{
ListNode *p = head, *q = NULL;
while (p && strcmp(p->data,key))
{
q = p;
p = p->next;
}
if (p != NULL)
{
q->next = p->next;
free(p);
}
else
printf("结点不存在\n");
}
//===========打印链表=======
void printlist(LinkList head)
{
ListNode *p=head->next; //从开始结点打印
while (p) {
printf("%s, ",p->data);
p=p->next;
}
printf("\n");
}
//==========删除所有结点，释放空间===========
void DeleteAll(LinkList head)
{
ListNode *p;
while (head)
{
p = head;
head = head->next;
free(p);
}
printf("All data has been deleted!");
}
代码分析
创建链表参考：C 语言学习回顾 - 404！v|+_+|v 404！
理解这些概念的最好方法是画个流程图
输入数据为bat，cat，eat，fat，hat，jat，lat，mat，#
头插法创建链表
//==========用头插入法建立带头结点的单链表===========
LinkList CreatList(void)
{
LinkList head; // 定义头指针
head = (ListNode *)malloc(sizeof(ListNode)); // 为头指针分配内存空间
head->next = NULL; // 头指针的指向地址赋空值
ListNode *p = NULL; // 定义一个指针p来接收赋值和传递地址
while(1)
{
printf("Input # to end ");
printf("Please input Node_data:");
char ch[10];
scanf("%s", ch); // 数组形式不用取地址符号&
if(strcmp(ch,"#")) // strcmp判断ch是否等于#，若等于则返回0，否则返回其他数
{
if(LocateNode(head,ch)==NULL) // 转到判断是否输入重复字符串
{
p = (ListNode *)malloc(sizeof(ListNode)); // 为p指针分配内存空间
strcpy(p->data, ch); // 这里因为ch为char类型，不能直接赋值，而应使用strcpy
p->next = head->next; // 将head的next指针指向p的下一节点
head->next = p; // head向后移
}
else
printf("You have already input this Node_data!\n"); // 重复
}
else
{
break;
}
}
return head;
}补充：
- strcmp用法：
- strcpy():用来将字符串的值赋给指针，直接使用=会报错
结果展示
尾插法创建链表
//==========用尾插入法建立带头结点的单链表===========
LinkList CreatListR1(void)
{
LinkList head;
head = (LinkList)malloc(sizeof(LinkList));
head->next = NULL;
ListNode *p, *q = head;
while(1)
{
printf("Input # to end ");
printf("Please input Node_data:");
char ch[10];
scanf("%s",ch);
if(strcmp(ch,"#"))
{
if(LocateNode(head,ch)==NULL)
{
p = (ListNode *)malloc(sizeof(ListNode));
strcpy(p->data, ch);
p->next = NULL; // 这一步真重要，之前一直卡在这里，若没赋空值，赋给p后，进入LocateNode判断会报错，因为q->next->next不是个地址同时也不为空！
q->next = p;
q = p;
// p->next = NULL;
}
}
else
break;
}
q->next = NULL;
return head;
}结果展示
查找
//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode *LocateNode(LinkList head, char *key)
{
ListNode *p = head->next;
while (p && strcmp(p->data,key))
{
p = p->next;
}
return p;
}结果展示
结合创建、增加、删除操作
增加
//==========增加节点=======
ListNode * AddNode(LinkList head)
{
ListNode *p = head->next;
printf("Please input Node_data:");
char ch[10];
scanf("%s", ch);
if(LocateNode(head,ch)==NULL)
{
p = (ListNode *)malloc(sizeof(ListNode));
strcpy(p->data, ch);
p->next = head->next;
head->next = p;
}
else
printf("You have already input this Node_data!\n");
return head;
}结果展示
删除
//==========删除带头结点的单链表中的指定结点=======
void DeleteList(LinkList head, char *key)
{
ListNode *p = head, *q = NULL;
while (p && strcmp(p->data,key))
{
q = p;
p = p->next;
}
if (p != NULL)
{
q->next = p->next;
free(p);
}
else
printf("结点不存在\n");
}结果展示
打印链表
//===========打印链表=======
void printlist(LinkList head)
{
ListNode *p=head->next; //从开始结点打印
while (p) {
printf("%s, ",p->data);
p=p->next;
}
printf("\n");
}删除所有结点
//==========删除所有结点，释放空间===========
void DeleteAll(LinkList head)
{
ListNode *p;
while (head)
{
p = head;
head = head->next;
free(p);
}
printf("All data has been deleted!");
}结果展示
1 条评论
目前没人能看到