以单链表作为存储结构,将线性表拓展2倍,假设线性表为(a1,a2,a3…aan,拓展后为(a1,a1a2,a2,…an,an)告诉我它的C语言源代码
时间: 2024-10-07 20:04:36 浏览: 24
设双链表表示的线性表L=(a1,a2,……,an),试写一时间复杂度为O(n)的算法,将L改造为L=(a1,a3,……,an,……,a4,a2)。
为了将单链表拓展2倍,我们需要创建一个新的节点,并将其插入到原链表的适当位置。这里是一个简单的C语言示例,用于说明如何实现这个过程:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
char data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(char data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 扩展链表函数
void doubleLinkedList(Node** head) {
if (*head == NULL) {
printf("链表为空,无法扩展。\n");
return;
}
Node* oldHead = *head;
Node* newHead = oldHead;
while (oldHead->next != NULL) {
Node* newNode = createNode(oldHead->data);
newNode->next = oldHead->next;
oldHead->next = newNode;
oldHead = oldHead->next;
}
// 将旧头节点添加到最后
newNode->next = oldHead;
}
// 遍历并打印链表
void printList(Node* head) {
while (head != NULL) {
printf("%c ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
// 初始化链表
Node* list = createNode('a');
list->next = createNode('b');
list->next->next = createNode('c'); // ... 继续添加元素
// 打印原始链表
printf("原始链表: ");
printList(list);
// 扩展链表
doubleLinkedList(&list);
// 打印拓展后的链表
printf("拓展后的链表: ");
printList(list);
return 0;
}
```
这段代码首先定义了一个链表节点结构体,然后创建一个`doubleLinkedList`函数来扩展链表,以及一个辅助函数`printList`来遍历和打印链表。在`main`函数中,我们创建了一个简单的链表,并展示了如何使用该函数进行扩展。
阅读全文