SDUT链表pta
时间: 2025-04-21 18:40:36 浏览: 40
### 关于SDUT(山东理工大学)链表PTA练习题
#### 插入元素保持顺序表有序
对于已知递增有序的顺序表 \( L \),为了将新元素 \( X \) 插入到合适的位置以维持其有序性,可以遍历整个列表找到第一个大于等于 \( X \) 的位置,在该处插入 \( X \)[^1]。
```c
void InsertInOrder(SqList *L, ElemType x){
int i;
for(i=(*L).length; i>0 && (*L).data[i-1]>x; --i)
(*L).data[i]=(*L).data[i-1];
if(i>=0&&i<=(*L).length)(*L).data[i]=x;
++(*L).length;
}
```
此代码片段展示了如何在一个已经按照升序排列好的数组 `SqList` 中插入一个新的数值 `ElemType x` 同时确保整体序列仍然保持从小到大排序。
#### 构建逆向单链表
另一个常见的操作是从标准输入读取一系列正整数直到遇到 `-1` 停止,并依据这些数字创建一个指向头部节点的指针所表示的单项链表;值得注意的是这个过程会使得最终形成的链表中的元素呈现反向次序[^2]。
```c
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* CreateList() {
struct ListNode head = { .next=NULL }, *p=&head;
while(1) {
scanf("%d", &(p->val));
if(p->val==-1 || getchar()!= '\n') break;
p=p->next=(struct ListNode*)malloc(sizeof(struct ListNode));
p->next=NULL;
}
return Reverse(head.next);
}
// Helper function to reverse the list.
struct ListNode* Reverse(struct ListNode* h) {
struct ListNode dummy={.next=h}, *cur=dummy.next,*prev=&dummy;
while(cur!=NULL){
struct ListNode* tmp=cur->next;
cur->next=prev;
prev=cur;
cur=tmp;
}
if(dummy.next != NULL) dummy.next->next = NULL;
return prev;
}
```
上述 C 语言程序实现了从终端接收一串非负整数形成一条带头结点且成员依次递减的循环双向链表的功能。请注意这里额外提供了一个辅助方法用于翻转原始构建出来的单向不带环路的数据结构实例以便满足题目关于“逆序”的具体需求。
阅读全文
相关推荐


















