【数据结构】【线性表】单链表4—单链表的建立(附C语言源码)

析木不会编程

1043人浏览 · 2024-11-12 18:36:02

析木不会编程 · 2024-11-12 18:36:02 发布

相关链接：
单链表的概念
 单链表的建立
 单链表的删除

强调：文中的所有ElemType指代任意变量，例如char、float、int甚至其它结构体变量；部分源码使用的是char，均经过作者验证可直接食用

单链表的建立

单链表的建立其实就是一个结点插入的过程，首先构建链表的结点结构体，并进行初始化，然后再不断插入结点，我们需要解决的问题是：

用什么插入方式？
在哪个位置插入？
程序如何设计：要不要头结点？单链表的长度是多少？链表每个元素内容又是什么？

[!插入方式的选用]
我们首先回答是选用哪种插入方式的问题？如果只看结果的话，构建单链表无所谓其哪种插入方式，只要能实现单链表的建立，都可以选用。但不同的插入方式有不同特点，在实际使用中，面对同一个问题的编程难易程度不一样，时间复杂度或者空间复杂度也会不一样。
回顾我们关于单链表的插入问题，我们一般有按位序插入和指定结点的前插和后插。按位序插入，位序说明本身就链表就已经存在，一般是用在某一个单链表的某个位置进行插入，指定结点插入分前插和后插，由于单链表的不可逆性，前插操作需要找到前驱结点，这个过程需要经过类似于按位序插入的遍历结点的过程，比较复杂，而指定结点的后插只需要指定结点，一切顺理成章，操作简单，时间复杂度低。

[!] 插入位置的选用
在哪个位置插入，无非就是，头部、尾部和中间。每次我们都将结点插入到头部，相当于一个倒序插入，而每次插入到尾部即为顺序插入，如果插入到中间则是无序，无序的线性表一般来说没有意义，因此我们用的最多的是头部插入和尾部插入，同时尾部插入又是最常用的插入方式。

[!如何设计程序]
当我们建立链表的时候，我们需要解决三个问题，第一个是要不要头结点？另一个是链表有多长？最后一个是链表的结点数据是什么？其实在这里就会出现很多结果，例如：有头结点和没有头结点，长度已知和长度未知都是有可能的，每一个结点数据是什么，是传递结点还是传递结点数据，理论上各有写法。
但在实际的应用中，我们希望我们的程序，结构简单，逻辑清晰，还有就是可拓展性强。考虑到这些，我们一般设计成一个动态长度，且传递结点元素的有头结点的单链表。
有头结点的在程序设计上相对简单，动态长度在一定程度上能够实现静态长度的功能，传递结点数据，比传递结点更具有实际应用意义也兼容传递结点的功能（此段有疑惑可以在评论区讨论或者私信我，在此不作大篇幅的论述）

结合上述回答，在此，我们设计尾插和头插两个单链表建立的程序

//首先，无论用什么方法，我们先建立单链表的结点结构体
typedef struct LNode{//定义单链表结点类型
	char data;//每一个结点存放一个数据元素
	struct LNode *next;//指针指向下一个结点
}LNode,*LinkList;

LinkList List_TailInsert(LinkList *L) {
    char flag = 's'; // 链表创建标志，s表示开始/继续创建链表结点
    char x; // 结点数据，ElemType指代任意数据类型，例如int

    *L = (LinkList)malloc(sizeof(LNode)); // 创建头结点
    if (*L == NULL) {
        printf("空间申请失败\n");
        exit(1);//终止程序 
    }
    (*L)->next = NULL;
    LNode *s, *r = *L; // s表示需要创建的当前结点，r指向尾结点

    while (flag == 's') { // 标志符为 s 则创建结点
        printf("输入结点数据: ");
        scanf(" %c", &x); // 输入结点数据 %e指代任意数据类型，例如%d，%s %f
        // 在r结点后插入元素x
        s = (LNode *)malloc(sizeof(LNode)); // 申请结点空间
        if (s == NULL) {
            printf("空间申请失败\n");
            exit(1);//终止程序 
        }
        s->data = x; // 将接收数据赋值给创建的当前结点s
        s->next = NULL; // 当前结点为末尾结点，后续暂时无结点
        r->next = s; // 此时s为尾结点

        r = s; // 更新尾结点，r始终指向尾结点
        printf("是否继续添加结点；是输入's'，不是输入任意数据: ");
        scanf(" %c", &flag); // 继续输入标志符，判断是否继续创建新结点
    }
    return *L; // 返回链表头结点
}

如果该链表没有头结点，则需要在创建第一个结点时特殊处理。没有头结点的第一个结点创建时，由于没有前驱结点，r->next=s中的r->next不存在，因此需要将该语句改为L=s，表示链表头指针指向当前结点s(第一个结点);因此s为尾结点其实还有一个更简单的方式，只需要引入一个变量length，表示当前链表长度，在length=1时作特殊处理。程序可以改为如下：

LinkList List_TailInsert(LinkList *L, int *length) {
    char flag = 's'; // 链表创建标志，s表示开始/继续创建链表结点
    char x; // 结点数据，ElemType指代任意数据类型，例如int
    LNode *s, *r = NULL; // s表示需要创建的当前结点，r指向尾结点
    *length = 0;

    printf("Enter 's' to start creating nodes: ");
    scanf(" %c", &flag); // 接收标志符
    while (flag == 's') { // 标志符为 s 则创建结点
        (*length)++; // 结点长度+1
        printf("Enter node data: ");
        getchar(); // 清除输入缓冲区中的残留字符
        scanf("%c", &x); // 输入结点数据 %e指代任意数据类型，例如%d，%s %f
        
        // 在r结点后插入元素x
        s = (LNode *)malloc(sizeof(LNode)); // 申请结点空间
        if (s == NULL) {
            printf("Memory allocation failed\n");
            exit(1);
        }
        s->data = x; // 将接收数据赋值给创建的当前结点s
        s->next = NULL; // 当前结点为末尾结点，后续暂时无结点
        if (*length == 1) {
            *L = s; // 链表头指针指向第一个结点
        } else {
            r->next = s; // 此时s为尾结点
        }

        r = s; // 更新尾结点，r始终指向尾结点
        printf("Do you want to continue? (s for yes, any other key for no): ");
        getchar(); // 清除输入缓冲区中的残留字符
        scanf(" %c", &flag); // 继续输入标志符，判断是否继续创建新结点
    }
    if (r != NULL) {
        r->next = NULL; // 为结点指针置空
    }
    return *L; // 返回链表头结点
}

该函数不仅减少了代码量，同时可以获取链表长度，但length++和多加了一条判断语句，一定程度上增加了算法的时间复杂度。
接下来简单介绍一下头插法的单链表的创建，头插法就是在头结点后面不断插入新结点，由于新结点每次都插入在头结点之后，所以获得的链表数据的顺序和输入的顺序是相反的。头插法和尾插法相识，但不需要r一直指向表尾了，因为链表开始创建之后头结点一般不会发生改变即表头不变，只需要尾插法的代码作个小小改进即可。

LinkList List_HeadInsert(LinkList &L){
	char flag='s';//链表创建标志，s表示开始/继续创建链表结点
	
	ElemType x;//结点数据，ElemType指代任意数据类型，例如int
	
	L=(LinkList)malloc(sizeof(LNode));//创建头结点
	L->next=NULL;
	LNode *s;//s表示需要创建的当前结点
	
	scanf("%s",flag);//接收标志符
	while(flag=='s'){//标志符为 s 则创建结点
		scanf("%e",x);//输入结点数据 %e指代任意数据类型，例如%d，%s %f
		//在头结点后插入元素x
		s=(LNode *)malloc(sizeof(LNode))//申请结点空间
		s->data=x;//将接收数据赋值给创建的当前结点s
		s->next=L->next;//当前结点的next继承头结点的next，指向原来的第一个结点
		L->next=s;//更新头节点的next指针，s为新的第一个结点

		scanf("%s",flag);//继续输入标志符，判断是否继续创建新结点
	}
	return L;//返回链表头结点
}

尾插法的链表各个结点数据与数据输入顺序一致，而头插法刚好相反，如果相同的结点数据，分别用头插法和尾插法创建一个链表，头插法的链表为尾插法链表的逆置。
如何将尾插法的顺序链表逆置呢？只需要将尾插法的按顺序读取并采用头插的方式重新创建链表：

LinkList List_Tail_Head(LinkList &T,LinkList,&H){
	char flag='s';//链表创建标志，s表示开始/继续创建链表结点
	
	ElemType x;//结点数据，ElemType指代任意数据类型，例如int
	if(T->next==NULL)//判断链表是否为空表
		return NULL;//链表为空表返回空链表
	H=(LinkList)malloc(sizeof(LNode));//创建头结点
	H->next=NULL;
	LNode *s,*r=T->next;//s表示需要创建的当前结点,s表示尾插法的当前结点
	
	scanf("%s",flag);//接收标志符
	while(r!=NULL){//尾插法当前结点数据存在则取出放头插法
		//在头结点后插入尾插法的对应元素
		s=(LNode *)malloc(sizeof(LNode))//申请结点空间
		
		s->data=r->data;//将尾插法的当前结点数据给创建的当前结点s
		
		s->next=H->next;//当前结点的next继承头结点的next，指向原来的第一个结点
		H->next=s;//更新头节点的next指针，s为新的第一个结点
		
		r=r->next;//尾插法当前结点移动一位
	}
	return H;//返回链表头结点
}