数据结构与算法~单链表

博主： Xherlock
发布时间：2021 年 09 月 16 日
614 次浏览
1 条评论
11524字数
分类：数据结构与算法

# 数据结构与算法——实验一

## 链表

### 题目要求

~~~
实验题目：单链表的基本操作

实验目的：
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：
建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。

实验主要步骤：
1、	分析、理解给出的示例程序。
2、	调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。
3、	修改程序：
（1）	增加插入结点的功能。
（2）	增加建立链表的尾插入法。
~~~

### 初始代码

~~~c
#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;
}

~~~

### 代码实现

//==========主函数==============

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！](http://120.78.215.15/index.php/archives/8/)

理解这些概念的最好方法是画个流程图

输入数据为bat，cat，eat，fat，hat，jat，lat，mat，\#

#### 头插法创建链表

~~~c
//==========用头插入法建立带头结点的单链表===========
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用法：![image-20210916213143801.png][1]
* strcpy():用来将字符串的值赋给指针，直接使用=会报错

##### 结果展示

![image-20210922172912830.png][2]

#### 尾插法创建链表

~~~c
//==========用尾插入法建立带头结点的单链表===========
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; 
}
~~~

##### 结果展示

![image-20210916213955278.png][3]

#### 查找

~~~c
//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode *LocateNode(LinkList head, char *key)
{
    ListNode *p = head->next;
    while (p && strcmp(p->data,key))
    {
        p = p->next;
    }
    return p;
}
~~~

##### 结果展示

结合创建、增加、删除操作

![image-20210916215137077.png][4]

#### 增加

~~~c
//==========增加节点=======
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;
}
~~~

##### 结果展示

![image-20210916214753521.png][5]

#### 删除

~~~c
//==========删除带头结点的单链表中的指定结点=======
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");
}
~~~

##### 结果展示

![image-20210916214317344.png][6]

#### 打印链表

~~~c
//===========打印链表=======
void printlist(LinkList head)
{
    ListNode *p=head->next;       //从开始结点打印
    while (p) {
		printf("%s,   ",p->data);
		p=p->next;
    }
    printf("\n");
}
~~~

#### 删除所有结点

~~~c
//==========删除所有结点，释放空间===========
void DeleteAll(LinkList head)
{
    ListNode *p;
    while (head)
    {
        p = head;
        head = head->next;
        free(p);
    }
    printf("All data has been deleted!");
}
~~~

##### 结果展示

![image-20210916214841505.png][7]

[1]: http://120.78.215.15/usr/uploads/2021/09/2201543000.png
[2]: http://120.78.215.15/usr/uploads/2021/09/2434038168.png
[3]: http://120.78.215.15/usr/uploads/2021/09/881175246.png
[4]: http://120.78.215.15/usr/uploads/2021/09/958426220.png
[5]: http://120.78.215.15/usr/uploads/2021/09/1824758385.png
[6]: http://120.78.215.15/usr/uploads/2021/09/835900821.png
[7]: http://120.78.215.15/usr/uploads/2021/09/3149019292.png

最后修改：2021 年 10 月 25 日

如果觉得我的文章对你有用，请随意赞赏

1 条评论

Xherlock
September 17th, 2021 at 06:14 pm

目前没人能看到

回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

pytorch数据处理
浏览次数: 360
彩色打字效果
浏览次数: 565
Sqli-labs学习1
浏览次数: 897
机试day11
浏览次数: 321
为数据快速添加引号
浏览次数: 777

数据结构与算法~单链表

Xherlock • 2021 年 09 月 16 日

# 数据结构与算法——实验一

## 链表

### 题目要求

~~~
实验题目：单链表的基本操作

实验目的：
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：
建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。

### 初始代码

//==========主函数==============

printlist(head);
	DeleteAll(head);            //删除所有结点，释放内存
}
//==========用尾插入法建立带头结点的单链表===========
LinkList CreatListR1(void)
{
}

//==========用头插入法建立带头结点的单链表===========
LinkList CreatList(void)
{

//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode *LocateNode(LinkList head, char *key)
{
}

//==========增加节点=======
ListNode * AddNode(LinkList head)
{
}

~~~

### 代码实现

//==========主函数==============

~~~

### 代码分析

创建链表参考：[C 语言学习回顾 - 404！v|+_+|v 404！](http://120.78.215.15/index.php/archives/8/)

理解这些概念的最好方法是画个流程图

输入数据为bat，cat，eat，fat，hat，jat，lat，mat，\#

#### 头插法创建链表

补充：

* strcmp用法：![image-20210916213143801.png][1]
* strcpy():用来将字符串的值赋给指针，直接使用=会报错

##### 结果展示

![image-20210922172912830.png][2]

#### 尾插法创建链表

##### 结果展示

![image-20210916213955278.png][3]

#### 查找

##### 结果展示

结合创建、增加、删除操作

![image-20210916215137077.png][4]

#### 增加

##### 结果展示

![image-20210916214753521.png][5]

#### 删除

##### 结果展示

![image-20210916214317344.png][6]

#### 打印链表

#### 删除所有结点

##### 结果展示

![image-20210916214841505.png][7]

1 条评论

发表评论 取消回复

数据结构与算法~单链表

发表评论取消回复