用C语言构造一个单链表程序,要求 (1)构造一个空的单链表L,其基本操作为LinkListInit(LinkList *L)。 (2)单链表L已存在,销毁单链表L,其基本操作为DestroyLinkList (LinkList *L)。 (3)单链表L已存在,若单链表L为空表,则返回0,否则返回1,调用函数可通过判断函数返回值确定结果状态,其基本操作为LinkListEmpty(LinkList *L)。 (4)单链表L已存在,返回单链表L中数据元素个数,其基本操作为LinkListLength (LinkList *L)。 (5)L为带头结点的单链表的头指针。当第i个元素存在时,返回其值,若这样的数据元素不存在,则给出相应的提示,其基本操作为GetLinkListElem(LinkList *L)。 (6)单链表L已存在,返回单链表L中第i个与e值相同的数据元素的位序,若这样的数据元素不存在,则给出相应的提示,其基本操作为LocateLinkListElem (LinkList *L, ElemType e)。 (7)在带头结点的单链表L中第i个位置之前插入元素e,若这样的数据元素不存在,则给出相应的提示,其基本操作为LinkListInsert(LinkList *L, int i, ElemType e)。 (8)在带头结点的单链表L中删除第i个元素,若这样的数据元素不存在或i值不符合要求,则给出相应的提示,其基本操作为LinkListDelete(LinkList *L, int i)。 (9)单链表L已存在,输出显示单链表L中的各个元素,其基本操作为DispLinkList(LinkList *L)。 (10) 头插法建立单链表L,其基本操作为CreateLinkListF(LinkList *L, ElemType d[ ], int n)。 (11) 尾插法建立单链表L,其基本操作为CreateLinkListR(LinkList *L, ElemType d[ ], int n)。
时间: 2024-03-26 19:40:45 浏览: 80
c语言实现链表的基本操作,链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
以下是您所要求的C语言单链表程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结点的结构体
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkList;
// 构造一个空的单链表L
void LinkListInit(LinkList *L) {
(*L) = (LinkList) malloc(sizeof(Node));
(*L)->next = NULL;
}
// 销毁单链表L
void DestroyLinkList(LinkList *L) {
LinkList p, q;
p = (*L)->next;
while (p != NULL) {
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
}
// 判断单链表L是否为空表
int LinkListEmpty(LinkList *L) {
return (*L)->next == NULL;
}
// 返回单链表L中数据元素个数
int LinkListLength(LinkList *L) {
int count = 0;
LinkList p = (*L)->next;
while (p != NULL) {
count++;
p = p->next;
}
return count;
}
// 返回单链表L中第i个元素的值
int GetLinkListElem(LinkList *L, int i) {
int j = 0;
LinkList p = (*L)->next;
while (p != NULL && j < i) {
p = p->next;
j++;
}
if (p == NULL || j > i) {
printf("第%d个元素不存在\n", i);
exit(1);
}
return p->data;
}
// 返回单链表L中第一个值为e的数据元素的位序
int LocateLinkListElem(LinkList *L, int e) {
int i = 0;
LinkList p = (*L)->next;
while (p != NULL && p->data != e) {
p = p->next;
i++;
}
if (p == NULL) {
printf("元素%d不存在\n", e);
return -1;
}
return i;
}
// 在单链表L的第i个位置之前插入元素e
void LinkListInsert(LinkList *L, int i, int e) {
int j = 0;
LinkList p = (*L), s;
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || j > i - 1) {
printf("无法插入元素\n");
exit(1);
}
s = (LinkList) malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
}
// 删除单链表L中第i个元素
void LinkListDelete(LinkList *L, int i) {
int j = 0;
LinkList p = (*L), q;
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || j > i - 1 || p->next == NULL) {
printf("无法删除元素\n");
exit(1);
}
q = p->next;
p->next = q->next;
free(q);
}
// 输出显示单链表L中的各个元素
void DispLinkList(LinkList *L) {
LinkList p = (*L)->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 头插法建立单链表L
void CreateLinkListF(LinkList *L, int d[], int n) {
(*L) = (LinkList) malloc(sizeof(Node));
(*L)->next = NULL;
LinkList p;
for (int i = 0; i < n; i++) {
p = (LinkList) malloc(sizeof(Node));
p->data = d[i];
p->next = (*L)->next;
(*L)->next = p;
}
}
// 尾插法建立单链表L
void CreateLinkListR(LinkList *L, int d[], int n) {
(*L) = (LinkList) malloc(sizeof(Node));
(*L)->next = NULL;
LinkList p, q = (*L);
for (int i = 0; i < n; i++) {
p = (LinkList) malloc(sizeof(Node));
p->data = d[i];
q->next = p;
q = p;
}
q->next = NULL;
}
int main() {
LinkList L;
int d[] = {1, 2, 3, 4, 5};
int n = sizeof(d) / sizeof(int);
// 构造一个空的单链表L
LinkListInit(&L);
// 头插法建立单链表L
CreateLinkListF(&L, d, n);
printf("头插法建立单链表L:");
DispLinkList(&L);
// 尾插法建立单链表L
CreateLinkListR(&L, d, n);
printf("尾插法建立单链表L:");
DispLinkList(&L);
// 返回单链表L中数据元素个数
printf("单链表L中数据元素个数:%d\n", LinkListLength(&L));
// 返回单链表L中第3个元素的值
printf("单链表L中第3个元素的值:%d\n", GetLinkListElem(&L, 3));
// 返回单链表L中第一个值为3的数据元素的位序
printf("单链表L中第一个值为3的数据元素的位序:%d\n", LocateLinkListElem(&L, 3));
// 在单链表L的第3个位置之前插入元素6
LinkListInsert(&L, 3, 6);
printf("在单链表L的第3个位置之前插入元素6:");
DispLinkList(&L);
// 删除单链表L中第4个元素
LinkListDelete(&L, 4);
printf("删除单链表L中第4个元素:");
DispLinkList(&L);
// 销毁单链表L
DestroyLinkList(&L);
return 0;
}
```
以上程序实现了您所要求的所有基本操作。需要注意的是,本程序实现的是整型单链表,如果需要存储其他类型的数据,需要修改定义单链表结点的结构体和相关函数的参数和返回值类型。
阅读全文