文章目录

线性表的链式存储结构

  • 将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块，称为结点，通过地址或指针建立元素之间的联系

  • 结点的data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的结点

  • 节点类型描述：
typedef  struct  node  {   
    data_t   data;   //结点的数据域//
    struct node *next;  //结点的后继指针域//
} listnode, *linklist;
  • 设p指向链表中结点ai

  • 获取ai，写作：p->data
  • 而取ai+1,写作：p->next->data
  • 若指针p的值为NULL，则它不指向任何结点，此时取p->data或p->next是错误的
  • 调用C语言中malloc()函数向系统申请结点的存储空间
    • linklist p;
    • p = (linklist)malloc(sizeof(listnode))
  • 则创建一个类型为linklist的结点，且该结点的地址已存入指针变量p中：

单链表创建

  • 依次读入表L=(a0,…,an-1)中每一元素ai(假设为整型)，若ai≠结束符（-1），则为ai创建一结点，然后插入表尾，最后返回链表的头结点指针H
  • 设L=(2，4，8，-1)，则建表过程如下：

  • 链表的结构是动态形成的，即算法运行前，表结构是不存在的

单链表查找

按序号查找

  • 实现GetLinklist(h, i)运算
  • 算法思路：从链表的a0起，判断是否为第i结点，若是则返回该结点的指针，否则查找下一结点，依次类推

按值查找（定位）

  • 即实现Locate(h, x)
  • 算法思路：从链表结点a0起，依次判断某结点是否等于x，若是，则返回该结点的地址，若不是，则查找下一结点a1,依次类推。若表中不存在x,则返回NULL

单链表插入

  • 即实现InsertLinklist(h, x, i,)，将x插入表中结点ai之前的情况
  • 算法思路：调用算法GetLinklist(h, i-1)，获取结点ai-1的指针p(ai 之前驱)，然后申请一个q结点，存入x，并将其插入p指向的结点之后

单链表删除

  • 即实现DeleteLinklist(h, i)
  • 算法思路：同插入法，先调用函数GetLinklist(h, i-1),找到结点ai的前驱，然后将结点ai删除

单链表倒置

  • 算法思路：依次取原链表中各结点，将其作为新链表首结点插入H结点之后

求相邻两结点data值之和为最大的第一结点指针

  • 设结点data域为整型，求链表中相邻两结点data值之和为最大的第一结点的指针
  • 算法思路：设p,q 分别为链表中相邻两结点指针，求p->data+q->data为最大的那一组值，返回其相应的指针p即可

合并链表且有序递增

  • 设两单链表A、B按data值（设为整型）递增有序，将表A和B合并成一表A，且表A也按data值递增有序
  • 算法思路：设指针p、q分别指向表A和B中的结点，若p->data ≤q->data则p结点进入结果表，否则q结点进入结果表

代码实现

功能代码

#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"

linklist list_create() {
	linklist H;

	H = (linklist)malloc(sizeof(listnode));
	if (H == NULL) {
		printf("malloc failed\n");
		return H;
	}
	
	H->data = 0;
	H->next = NULL;

	return H;
}

int list_tail_insert(linklist H, data_t value) {
	linklist p;
	linklist q;

	if (H == NULL) {
		printf("H is NULL\n");
		return -1;
	}

	if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
		printf("malloc failed\n");
		return -1;
	}
	p->data = value;
	p->next = NULL;
	
	q = H;
	while (q->next != NULL) {
		q = q->next;
	}

	q->next = p;

	return 0;
}

linklist list_get(linklist H, int pos) {
	linklist p;
	int i;

	if (H == NULL) {
		printf("H is NULL\n");
		return NULL;
	}

	if (pos == -1) {
		return H;
	}

	if (pos < -1) {
		printf("pos is invalid\n");
		return NULL;
	}

	p = H;
	i = -1;
	while (i < pos) {
		p = p->next;
		if (p == NULL) {
			printf("pos is invalid\n");
			return NULL;
		}
		i++;
	}

	return p;
}

int list_insert(linklist H, data_t value, int pos) {
	linklist p;
	linklist q;

	if (H == NULL) {
		printf("H is NULL\n");
		return -1;
	}

	p = list_get(H, pos-1);
	if (p == NULL) {
		return -1;
	}

	if ((q = (linklist)malloc(sizeof(listnode))) == NULL) {
		printf("malloc failed\n");
		return -1;
	}
	q->data = value;
	q->next = NULL;

	q->next = p->next;
	p->next = q;

	return 0;
}

int list_delete(linklist H, int pos) {
	linklist p;
	linklist q;

	if (H == NULL) {
		printf("H is NULL\n");
		return -1;
	}

	p = list_get(H, pos-1);
	if (p == NULL) 
		return -1;
	if (p->next == NULL) {
		printf("delete pos is invalid\n");
		return -1;
	}

	q = p->next;
	p->next = q->next;//p->next = p->next->next;

	printf("free:%d\n", q->data);
	free(q);
	q = NULL;

	return 0;
}

int list_show(linklist H) {
	linklist p;

	if (H == NULL) {
		printf("H is NULL\n");
		return -1;
	}

	p = H;

	while (p->next != NULL) {
		printf("%d ", p->next->data);
		p = p->next;
	}
	puts("");

	return 0;
}

linklist list_free(linklist H) {
	linklist p;

	if (H == NULL) 
		return NULL;

	p = H;

	printf("free:");
	while (H != NULL) {
		p = H;
		printf("%d ", p->data);
		free(p);
		H = H->next;
	}
	puts("");

	return NULL;
}

int list_reverse(linklist H) {
	linklist p;
	linklist q;

	if (H == NULL) {
		printf("H is NULL\n");
		return -1;
	}

	if (H->next == NULL || H->next->next == NULL) {
		return 0;
	}

	p = H->next->next;
	H->next->next = NULL;

	while (p != NULL) {
		q = p;
		p = p->next;

		q->next = H->next;
		H->next = q;
	}

	return 0;
}

linklist list_adjmax(linklist H, data_t *value) {
	linklist p, q, r;
	data_t sum;

	if (H == NULL){
		printf("H is NULL\n");
		return NULL;
	}

	if (H->next == NULL || H->next->next == NULL || H->next->next->next == NULL) {
		return H;
	}

	q = H->next;
	p = H->next->next;//p = q->next;
	r = q;
	sum = q->data + p->data;

	while (p->next != NULL) {
		p = p->next;
		q = q->next;
		if (sum < q->data + p->data) {
			sum = q->data + p->data;
			r = q;
		}
	}

	*value = sum;

	return r;
}

int list_merge(linklist H1, linklist H2) {
	linklist p, q, r;

	if (H1 == NULL || H2 == NULL) {
		printf("H1 || H2 is NULL\n");
		return -1;
	}

	p = H1->next;
	q = H2->next;
	r = H1;
	H1->next = NULL;
	H2->next = NULL;

	while (p && q) {
		if (p->data <= q->data) {
			r->next = p;
			p = p->next;
			r = r->next;
			r->next = NULL;
		} else {
			r ->next = q;
			q = q->next;
			r = r->next;
			r->next = NULL;
		}
	}

	if (p == NULL) {
		r->next = q;
	}else {
		r->next = p;
	}

	return 0;
}

头文件

typedef int data_t;

typedef struct node {
	data_t data;
	struct node * next;
}listnode, * linklist;

linklist list_create();
int list_tail_insert(linklist H, data_t value);//head
linklist list_get(linklist H, int pos);
int list_insert(linklist H, data_t value, int pos);
int list_delete(linklist H, int pos);
int list_show(linklist H);
linklist list_free(linklist H);
int list_reverse(linklist H);
linklist list_adjmax(linklist H, data_t *value);
int list_merge(linklist H1, linklist H2);

测试用例

#include <stdio.h>
#include "linklist.h"

void test_get();
void test_insert();
void test_delete();
void test_reverse();
void test_adjmax();

int main(int argc, const char *argv[])
{
	linklist H1, H2;
	int a[] = {1, 4, 6, 8, 10};
	int b[] = {2, 4, 16, 18, 30};
	int i;

	H1 = list_create();
	if (H1 == NULL)
		return;

	H2 = list_create();
	if (H2 == NULL)
		return;

	for (i = 0; i < sizeof(a)/sizeof(int); i++) {
		list_tail_insert(H1, a[i]);
	}

	for (i = 0; i < sizeof(b)/sizeof(int); i++) {
		list_tail_insert(H2, b[i]);
	}

	list_show(H1);
	list_show(H2);

	list_merge(H1, H2);
	printf("merge:\n");

	list_show(H1);
	list_show(H2);

	list_free(H1);
	list_free(H2);

	return 0;
}

void test_adjmax() {
	linklist H;
	linklist r;
	int value;
	int sum;
	
	H = list_create();
	if (H == NULL)
		return;

	printf("input:");
	while (1) {
		scanf("%d", &value);
		if (value == -1)
			break;
		list_tail_insert(H, value);
		printf("input:");
	}
	list_show(H);

	r = list_adjmax(H, &sum);
	if (r != NULL && r != H) {
		printf("data=%d, sum=%d\n", r->data, sum);
	}

	list_show(H);

	list_free(H);

}
void test_reverse() {
	linklist H;
	int value;
	
	H = list_create();
	if (H == NULL)
		return ;

	printf("input:");
	while (1) {
		scanf("%d", &value);
		if (value == -1)
			break;
		list_tail_insert(H, value);
		printf("input:");
	}
	
	list_show(H);
	list_reverse(H);
	list_show(H);

	list_free(H);

}

void test_delete() {
	linklist H;
	int value;
	
	H = list_create();
	if (H == NULL)
		return;

	printf("input:");
	while (1) {
		scanf("%d", &value);
		if (value == -1)
			break;
		list_tail_insert(H, value);
		printf("input:");
	}
	
	list_show(H);
	printf("H=%p\n", H);
	H = list_free(H);
	printf("H=%p\n", H);
	list_delete(H, -4);//1 3 5 7
	list_show(H);

	list_free(H);

}

void test_get() {
	linklist H;
	int value;
	linklist p;
	
	H = list_create();
	if (H == NULL)
		return;

	printf("input:");
	while (1) {
		scanf("%d", &value);
		if (value == -1)
			break;
		list_tail_insert(H, value);
		printf("input:");
	}
	
	list_show(H);

	p = list_get(H, 4);//1 3 5 7
	if (p != NULL)
		printf("value=%d\n", p->data);
}

void test_insert() {
	linklist H;
	int value;
	
	H = list_create();
	if (H == NULL)
		return;

	printf("input:");
	while (1) {
		scanf("%d", &value);
		if (value == -1)
			break;
		list_tail_insert(H, value);
		printf("input:");
	}
	
	list_show(H);
	list_insert(H, 100, 0);//1 3 5 7
	list_show(H);
}
# 数据结构
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

2026年最好用的5款降AI工具+免费降AI方法【建议收藏】

avatar 2048 AI社区

PHP使用CURL发送POST请求方法总结（API对接必备）

java RSA2 加密、解密 、签名和验证签名 https://blog.csdn.net/TaLinBoy/article/details/106124535。IOS：RSA2 加密、解密 、签名和验证签名 https://blog.csdn.net/TaLinBoy/article/details/106140526。详细请参考：https://blog.csdn.net/guyongqia

avatar 2048 AI社区

【AI Agent 开发实战】基于 LangGraph + Redis + FastAPI WebSocket 的分布式对话系统，支持多端实时同步和断点续传

在现代分布式系统中，实现多端多机器的用户对话系统面临以下挑战：本方案采用LangGraph作为对话状态管理框架，Redis作为分布式协调和状态存储中间件，WebSocket作为实时通信协议，构建一个完整的分布式对话系统。LangGraph是LangChain生态的扩展框架，专注于构建复杂、有状态的AI系统。其核心特性包括：Redis作为分布式系统的核心组件，提供以下功能：WebSocket提供全双

avatar 2048 AI社区