线性表的应用（有序表的合并、多项式运算、稀疏多项式运算、图书信息管理）

1、有序表的合并（链表实现）

# include<stdio.h>
# include<malloc.h> 
# include<stdlib.h>

typedef struct Node{
	int data;
	struct Node * pNext;
}NODE, * PNODE;

PNODE createList();
PNODE createList1(int len);
void listMerge(PNODE pHead1, PNODE pHead2, PNODE pHead3);
void traverseList(PNODE pHead);
int lengthList(PNODE pHead);

int main(void){
	int len = lengthList(pHead1) + lengthList(pHead2);; 
	PNODE pHead1 = NULL;
	PNODE pHead2 = NULL;
	PNODE pHead3 = NULL;
	
	//创建、遍历第一个链表 
	pHead1 = createList();
	traverseList(pHead1);
	//创建、遍历第二个链表 
	pHead2 = createList();
	traverseList(pHead2);
	
	//创建、合并、遍历输出第三个链表 
	pHead3 = createList1(len);
	listMerge(pHead1, pHead2, pHead3);
	traverseList(pHead3);
	retrun 0;
}

//创建链表（第一二个）
PNODE createList(){
	int i;
	int val;
	int len;
	
	printf("请输入链表的长度：len = ");
	scanf("%d", &len);
	
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if(NULL == pHead){
		printf("内存分配失败！");
		exit(-1);
	}
	
	PNODE pTail = pHead;
	pTail->pNext = NULL;
	
	for(i = 0; i< len; i++){
		printf ("请输入第%d个节点的值：val = ", i+1);
		scanf("%d", &val);
		
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if(NULL == pNew){
		printf("内存分配失败！");
		exit(-1);
		}
		
		//尾插法建立一个非循环单链表 
		pNew->data = val;
		pTail->pNext = pNew;
		pTail = pNew;
	} 
	pTail->pNext = NULL;
	return pHead;
}

//创建链表（第三个）
PNODE createList1(int len){
	int i;
	int val;
	
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if(NULL == pHead){
		printf("内存分配失败！");
		exit(-1);
	}
	
	PNODE pTail = pHead;
	pTail->pNext = NULL;
	
	for(i = 0; i < len; i++){
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if(NULL == pNew){
		printf("内存分配失败！");
		exit(-1);
		}
		
		//尾插法建立一个非循环单链表 
		pNew->data = 0;
		pTail->pNext = pNew;
		pTail = pNew;
	} 
	pTail->pNext = NULL;
	return pHead;
}

//合并链表
void listMerge(PNODE pHead1, PNODE pHead2, PNODE pHead3){
	int i;
	int len = lengthList(pHead3);
	PNODE p = pHead1->pNext;
	PNODE q = pHead2->pNext;
	PNODE x = pHead3->pNext;
	
	printf("test!!!"); 
		//两个有序表没有比较完的情况 
	while(NULL != p && NULL != q){
		if(p->data <= q->data)
			{
				x->data = p->data;
				p = p->pNext;
				x = x->pNext;
			} 
		else
			{
				x->data = q->data;
				q = q->pNext;
				x = x->pNext;
			}
			
	}
	//只剩下第一个链表的情况：将其剩余数据直接挂到第三个链表的最后
	while(NULL != p){
			x->data = p->data;
			p = p->pNext;
			x = x->pNext; 	
	}
	//只剩下第二个链表的情况：将其剩余数据直接挂到第三个链表的最后
	while(NULL != q){
			x->data = q->data;
			q = q->pNext;
			x = x->pNext;
	}
}

//遍历链表
void traverseList(PNODE pHead){
	PNODE p = pHead->pNext;
	while(NULL != p){
		printf("%d ", p->data);
		p = p->pNext;
	}
	printf("\n");
	return;
} 

//求链表的长度
int lengthList(PNODE pHead){
	int len = 0;
	PNODE p = pHead->pNext;
	while(NULL != p){
		len++;
		p = p->pNext;
	}
	return len;
}
**//总结：这个程序过于冗余，后面再优化看看。**

2、多项式运算（数组实现）