数据结构实习报告--单链表的插值

单链表的插值

二、实验内容与步骤

设单链表L是一个非递减有序表，试写算法将变量x的值插入其中之后仍保持L的有序性。

统一要求，在程序中构造三个子程序分别为：

LinkedList LinkedListCreate( ) /*建立链表*/

void InsertList(LinkedList L,int x) /*插入结点*/ void print(LinkedList L); /*输出链表中的结点*/ 代码

#include #include /* 单链表的结点类型 */ typedef struct LNode{ int data; LNode* next; }LNode,*LinkedList;

LinkedList LinkedListCreat( ) //建立链表 {

LinkedList head = (LNode*)malloc(sizeof(LNode)); head->next = NULL;

printf(\请输入链表大小：\\n\ int n,i,j,a[1000]; scanf(\

printf(\请输入链表的所有元素：\\n\ for(i=1;i<=n;i++) //输入元素 scanf(\ //冒泡排序 for(i=1;ia[j+1]){ int t;

t=a[j];a[j]=a[j+1];a[j+1]=t; } //尾插法创建链表 LinkedList p = head; for(i=1;i<=n;i++){

LinkedList t = (LNode*)malloc(sizeof(LNode)); t->data = a[i]; t->next = NULL; p->next = t; p = t; }

return head; }

void InsertList(LinkedList L,int x) //插入结点 {

LinkedList p = L->next,pre = L; while(p) {

if(x < p->data) //插在pre后面，p前面 {

LinkedList t = (LNode*)malloc(sizeof(LNode)); t->data = x; t->next = p; pre->next = t; break; } pre = p; p = p->next; }

if(p==NULL){ //如果这个数比链表中任何一个数都大 LinkedList t = (LNode*)malloc(sizeof(LNode)); t->data = x;

t->next = NULL; pre->next = t; } }

void print(LinkedList L) //输出链表中的结点 {

LinkedList p=L->next; while(p) {

printf(\ p = p->next; }

printf(\}

int main()//主函数 { int x;

LinkedList head = LinkedListCreat(); printf(\请输入要插入的元素值：\\n\ scanf(\

InsertList(head,x);

printf(\插入之后的单链表：\\n\ print(head); return 0; }