当前位置：首页 > news >正文

常规链表建立

news 2026/3/26 19:42:01

常规链表建立

列举常见的顺序表功能实现函数，进行编程练习

常规顺序表（sequeue）建立

定义一个顺序表的大小，结构体中采用数组而不是另一个堆内存空间表示存储的数据信息。

typedef int data_t; // 定义顺序表中数据元素的数据类型
#define N 20         // 定义顺序表的容量
typedef struct
{data_t data[N]; // 用数组作为顺序表存储空间int last; // last表示有效元素的下标（类比于数组下标）
}sqlist, *sqlink;

编程实现各种功能函数：

创建顺序表

sqlink list_create()
{sqlink L;L = (sqlink)malloc(sizeof(sqlist));//实现内容的空间申请，结合后续初始化；此处可以采用calloc函数进行优化处理。if (L == NULL)//判断内存是否申请成功{printf("list malloc failed!\n");return L;}memset(L, 0, sizeof(sqlist));L->last = -1;//当顺序表内容没任何值时，应该从-1算起；如果从0开始算，则表示一开始就有一个值。return L;
}

清空顺序表

判断函数是否成功时，返回值可以用整型int，或者布尔型bool表达。此处空表直接返回，不予清空。0代表成功，-1代表失败
```
int list_clear(sqlink L)
{if (L == NULL)return -1;memset(L, 0, sizeof(sqlist));L->last = -1;return 0;
}
```

释放顺序表申请的堆空间

int list_free(sqlink L)
{if (NULL == L)return -1;free(L);L = NULL;return 0;
}

删除顺序表中指定位置的数据

int list_delete(sqlink L, int pos)
{if (-1 == L->last){printf("list is empty");return -1;}if (pos < 0 || pos >= L->last)// 检查该指定位置是否合法{printf("The list is invalid\n");return -1;}int i = 0;for (i = pos; i <= L->last; i++)// 删除指定成员，即将该处后续元素依次往前覆盖{L->data[i] = L->data[i + 1];}L->last--;//最后更新last的值return 0;
}

检查顺序表是否为空表

int list_empty(sqlink L)
{if (L->last == -1)//当为空表时，下标last为-1return -1;elsereturn 0;
}

测量顺序表的长度

int list_length(sqlink L)
{if (L->last == -1)//当为空表时，下标last为-1，否则就有长度return -1;elsereturn (L->last + 1);
}

定位指定值在该顺序表的位置

int list_locate(sqlink L, data_t value)
{int i;for (i = 0; i < L->last; i++){if (L->data[i] == value)//利用便利，检测指定值在该顺序表的位置并返回return i;}return -1;
}

指定位置插入某个指定的值

int list_insert(sqlink L, data_t value, int pos)
{int i;if (L->last == N - 1)//判断空表{printf("The list is full\n");return -1;}if (pos < 0 || pos > L->last + 1)// 检查该指定位置是否合法{printf("Pos is invalid\n");return -1;}for (i = L->last; i >= pos; i--)//将指定位置处，后续的值都往后腾出一个位置，用来放指定的值。{L->data[i + 1] = L->data[i];}L->data[pos] = value;L->last++;return 0;
}

顺序表内容展示

int list_show(sqlink L)
{int i;if (L == NULL)return -1;if (L->last == -1)//空表就无需展示printf("list is empty.\n");for (i = 0; i <= L->last; i++)//利用for循环打印每个元素printf("%d ", L->data[i]);puts("");//遍历完成，输出回车以和别的函数区分return 0;
}

合并两个元素类型相同顺序表

int list_merge(sqlink L1, sqlink L2)//合并L1 和L2 顺序表，并消除相同元素
{int i = 0;int ret;while (i <= L2->last){ret = list_locate(L1, L2->data[i]);// ret 为-1时，即L2->data[i]在L1无重复元素，直接从尾部插入。if (ret == -1)list_insert(L1, L2->data[i], L1->last + 1);i++;}return 0;
}

删除单个顺序表中相同的元素

int list_purge(sqlink L)
{int i = 1;int j;if (L->last == 0)//判断顺序表是否仅一个元素return 0;while (i <= L->last){j = i - 1;while (j >= 0){if (L->data[i] == L->data[j])//存在相同元素时，进行删除操作{list_delete(L, i);break;}elsej--;if (j < 0)//内部遍历完成后，进行外部遍历，保证每个元素都进行对比i++;}}
}

常规顺序表功能调试

为了方便进行测试各个功能函数，本文将为每个测试都单独写成了一个函数，仅需进行单独调用即可进行测试，思路较为清晰。

函数主体如下，每次进行测试时，取消对应函数注释即可，并且尤其注意，如果是模块化编程，需要在主函数前进行函数声明。
```
int main(int argc, const char *argv[])
{//void test_delete();//void test_merge();test_purge();return 0;
}
```

各测试函数如下，符合模块化编程思想：

插入功能，及单顺序表合并测试

void test_purge()
{sqlink L;L = list_create();list_insert(L, 10, 0);list_insert(L, 20, 0);list_insert(L, 30, 0);list_insert(L, 20, 0);list_insert(L, 30, 0);list_show(L);list_purge(L);list_show(L);
}

删除测试

void test_delete()
{sqlink L;L = list_create();list_insert(L, 10, 0);list_insert(L, 20, 0);list_insert(L, 30, 0);list_insert(L, 40, 0);list_insert(L, 50, 0);list_show(L);list_delete(L, 15);list_show(L);
}

双顺序表合并测试

void test_merge()
{sqlink L1, L2;L1 = list_create();L2 = list_create();list_insert(L1, 10, 0);list_insert(L1, 20, 0);list_insert(L1, 30, 0);list_insert(L1, 40, 0);list_insert(L1, 50, 0);list_insert(L2, 30, 0);list_insert(L2, 40, 0);list_insert(L2, 60, 0);list_insert(L2, 70, 0);list_insert(L2, 80, 0);list_show(L1);list_show(L2);list_merge(L1, L2);list_show(L1);
}

查看全文

http://www.jsqmd.com/news/44839/