以C结构体或C++的“类”代替“第2章中复杂数据类型”,实现“链式线性表”,编写下面6个接口函数:CreateList、ListPrint、GetElem、ListLength、ListInsert、ListDelete
时间: 2023-05-28 14:05:21 浏览: 95
输入语句-C++语法和结构体
本质上,链式线性表可以看作是一个链表,每个节点存储一个元素,同时包含指向下一个节点的指针。因此,我们可以使用C结构体表示每个节点,使用指针表示整个链表。具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct ListNode {
int val; // 存储的元素
struct ListNode *next; // 指向下一个节点的指针
} ListNode;
// 创建链表
ListNode *CreateList() {
ListNode *head = NULL;
ListNode *p = NULL;
int val;
printf("请输入元素(输入0结束):");
scanf("%d", &val);
while (val != 0) {
ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
new_node->val = val;
new_node->next = NULL;
if (head == NULL) {
head = new_node;
p = new_node;
} else {
p->next = new_node;
p = p->next;
}
printf("请输入元素(输入0结束):");
scanf("%d", &val);
}
return head;
}
// 打印链表
void ListPrint(ListNode *head) {
ListNode *p = head;
while (p != NULL) {
printf("%d->", p->val);
p = p->next;
}
printf("NULL\n");
}
// 获取指定位置的元素
int GetElem(ListNode *head, int pos) {
ListNode *p = head;
int i = 0;
while (p != NULL && i < pos) {
p = p->next;
i++;
}
if (p == NULL) {
printf("位置无效\n");
return -1;
} else {
return p->val;
}
}
// 获取链表长度
int ListLength(ListNode *head) {
int len = 0;
ListNode *p = head;
while (p != NULL) {
len++;
p = p->next;
}
return len;
}
// 在指定位置插入元素
void ListInsert(ListNode **head, int pos, int val) {
if (pos < 0 || pos > ListLength(*head)) {
printf("位置无效\n");
return;
}
ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
new_node->val = val;
new_node->next = NULL;
if (pos == 0) {
new_node->next = *head;
*head = new_node;
} else {
ListNode *p = *head;
int i = 0;
while (i < pos - 1) {
p = p->next;
i++;
}
new_node->next = p->next;
p->next = new_node;
}
}
// 删除指定位置的元素
void ListDelete(ListNode **head, int pos) {
if (pos < 0 || pos >= ListLength(*head)) {
printf("位置无效\n");
return;
}
if (pos == 0) {
ListNode *p = *head;
*head = (*head)->next;
free(p);
} else {
ListNode *p = *head;
int i = 0;
while (i < pos - 1) {
p = p->next;
i++;
}
ListNode *q = p->next;
p->next = q->next;
free(q);
}
}
// 测试函数
int main() {
ListNode *head = CreateList();
ListPrint(head);
ListInsert(&head, 0, -1);
ListInsert(&head, 3, 3);
ListInsert(&head, 100, 100);
ListPrint(head);
printf("%d\n", GetElem(head, 2));
printf("%d\n", GetElem(head, 100));
printf("%d\n", ListLength(head));
ListDelete(&head, 0);
ListDelete(&head, 2);
ListDelete(&head, 100);
ListPrint(head);
return 0;
}
```
上述代码中,我们使用了指向指针的指针来修改头节点,因为头节点是链表的起点,需要在函数外部进行修改。同时,我们也使用了动态内存分配函数malloc和free,确保了链表的内存动态分配和释放。
阅读全文