用c++利用链式存储方式实现下列功能:根据键盘输入数据建立一个线性表,并输出该线性表;对该线性表进行数据的插入、删除、查找操作,并在插入和删除数据后,再输出线性表
时间: 2023-06-03 11:07:30 浏览: 630
好的,这是一个关于数据结构的问题,我可以回答。首先,链式存储方式是指使用指针来连接各个节点,构成一个链表。可以按照如下步骤实现该功能:
1.定义一个节点结构体:
```
typedef struct Node {
int data; // 数据
struct Node *next; // 指向下一个节点的指针
} Node;
```
2.定义一个链表结构体:
```
typedef struct List {
Node *head; // 指向链表头节点的指针
int length; // 链表长度
} List;
```
3.编写函数实现建立线性表、插入、删除和查找操作:
- 建立线性表
```
void createList(List *list) {
int n;
Node *p, *q;
printf("请输入要插入的元素个数:");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
p = (Node*)malloc(sizeof(Node));
printf("请输入第%d个元素的值:", i+1);
scanf("%d", &(p->data));
if (i == 0) { // 第一个节点
list->head = p;
} else {
q->next = p;
}
q = p;
}
p->next = NULL;
list->length = n;
printf("线性表的内容为:\n");
printList(list);
}
```
- 插入数据
```
void insertData(List *list) {
int position;
Node *p, *q;
printf("请输入要插入的元素位置和值(用空格隔开):");
scanf("%d %d", &position, &(p->data));
if (position < 1 || position > list->length+1) {
printf("插入位置不合法!\n");
return;
}
p = (Node*)malloc(sizeof(Node));
q = list->head;
for (int i = 1; i < position-1; i++) { // 找到被插入位置的前一个节点
q = q->next;
}
p->next = q->next;
q->next = p;
list->length++;
printf("插入数据后的线性表内容为:\n");
printList(list);
}
```
- 删除数据
```
void deleteData(List *list) {
int position;
Node *p, *q;
printf("请输入要删除的元素位置:");
scanf("%d", &position);
if (position < 1 || position > list->length) {
printf("删除位置不合法!\n");
return;
}
q = list->head;
if (position == 1) { // 删除头节点
list->head = q->next;
} else { // 删除其他位置的节点
for (int i = 1; i < position-1; i++) { // 找到被删除位置的前一个节点
q = q->next;
}
p = q->next;
q->next = p->next;
free(p);
}
list->length--;
printf("删除数据后的线性表内容为:\n");
printList(list);
}
```
- 查找数据
```
void searchData(List *list) {
int value;
Node *p;
bool found = false;
printf("请输入要查找的元素值:");
scanf("%d", &value);
p = list->head;
while (p != NULL) {
if (p->data == value) {
found = true;
break;
}
p = p->next;
}
if (found) {
printf("元素%d在线性表中的位置为:%d\n", value, getPosition(list, p));
} else {
printf("元素%d不存在于本线性表中!\n", value);
}
}
```
- 输出线性表
```
void printList(List *list) {
Node *p;
p = list->head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
```
以上就是利用链式存储方式实现线性表的建立、插入、删除和查找操作的方法。