|
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
typedef ElemType int;
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode;
typedef LNode *LinkList; //单链表类型名
void WarnMessage(char *s)
{
printf(s);
}
LNode* CreateNode(ElemType e)//创建结点
{
LNode *temp = (LNode*)malloc(sizeof(LNode));
temp->data = e;
temp->next = NULL;
return temp;
}
void DestoryList_Link(LinkList *LHead)//销毁单链表；
/*从头结点开始，释放每个结点的空间*/
{
if(NULL == *LHead)
{
WarnMessage("\nThere are no Nodes to be freed!\n");
return;
}
else{
LinkList p;
/*从头结点开始，一一释放结点的空间*/
while(*LHead){
p = (*LHead)->next;
free(*LHead);
*LHead = p;
}
}
}
int ListLength_Link(LinkList *LHead)//求链表长度；
/*通过遍历各结点，将长度length加一*/
{
int length = 0;//定义表长变量length并初始化为0；
if(NULL == *LHead)
{
return 0;
}
LNode *p = *LHead;
while(p){
length++;
p=p->next;
}
return length;
}
void ListInsert_Link(LinkList *LHead,int i,LNode *node)//在单链表中插入元素；
/*在单链表L中第i个位置之前插入值e的结点，1<=i<=表长+1；*/
{
if(NULL == *LHead){
*LHead = node;/*如果头结点指针域为空，则当前结点作为第一个结点*/
return ;
}
/*头结点指针域不为空,指针指向第一个结点
**移动指针，找到相应的插入位置；
*/
LNode *p = *LHead;
int k=0;
while(p && k<(i-1)){
k ++;
p = p->next;
}
if(!p ||(k > i-1)){
WarnMessage("Input Error,Insert Failed!\n");
}
else{
node->next = p->next;
p->next = node;
}
}
ElemType GetElem_Link(LinkList *LHead,int i)//某位置i取元素值；
{
ElemType re_data = 0;
if(NULL == *LHead){
return ERROR;
}
if(i>ListLength_Link(LHead)){
printf("input error!\n");
return ERROR;
}
LinkList Temp = *LHead;
int k = 0;
while(Temp && k<(i-1)){
Temp = Temp->next;
k++;
}
re_data = Temp->data;
return re_data;
}
State ListDelete_Link(LinkList *LHead,int i)//删除特定的元素。
/*在带头结点的单链表中，删除第i个元素*/
{
LinkList p,temp;
if(NULL == *LHead){
WarnMessage("NO Node to be deleted!");
return ERROR;
}
if(i>ListLength_Link(LHead)){
return ERROR;
}
p = *LHead;
int k = 0;
while(p->next && (k<i-1)){
p = p->next;
++k;
}
temp = p->next;
p->next = temp->next;
free(temp);
return OK;
}
int LocateElem_Link(LinkList *LHead,ElemType e)//定位元素的位置。
/*根据结点数据值，找到到其所在位置*/
{
LinkList p = *LHead;
int k=0;
while(p&&(p->data != e))
{
p=p->next;
++k;
}
return k;
}
void LNode_Traver(LinkList *LHead)
/*从头结点开始遍历整个链表*/
{
LinkList p = *LHead;
while(NULL != p)
{
printf("%d-->",p->data);
p = p->next;
}
WarnMessage("\n\n");
}
/*
**根据结点数据域的大小进行由大到小的排序
*/
/*这个排序方法不怎么实用
void Sort_LinkList(LinkList *LHead){
LinkList p,q,big;
Elemtype temp;
for(p = (*LHead)->next;p->next;p = p->next){
big = p;
for(q = p->next;q->next;q = q->next){
if(q->data > big->data){
big = q;
}
}
if(p != big){
temp = p->data;
p->data = big->data;
big->data = temp;
}
}
}
*/
//另一种单链表排序方法
void selectsort(LinkList *g)
{
LNode *p,*q,*t,*s,*h;
h=(LNode *)malloc(sizeof(LNode));
h->next=*g; /*h-->g的第一个结点*/
p=h; //p,h->同一地址
while(p->next->next!=NULL)
{
for(s=p,q=p->next;q->next!=NULL;q=q->next)
if(q->next->data<s->next->data)
s=q;
if(s!=q)
{
t=s->next;
s->next=t->next;
t->next=p->next;
p->next=t;
}
p=p->next;
}
*g=h->next;
free(h);
}
/*将两个单链表A,B归并成新的单链表C
**设置两个指针分别指向A，B的第一个结点，第三个指针指向空表
**当其中一个表为空时，表示其已并完，只需将另一表中元素归并到C中；
*/
void MergeList_L(LinkList *HeadA,LinkList *HeadB,LinkList *HeadC){
LinkList pa,pb,pc;
/*pa,pb分别指向第一个结点，pc作为新链表的头指针*/
pa = (*HeadA)->next;
pb = (*HeadB)->next;
*HeadC = pc = *HeadA; //将HeadA的头结点作为HeadC头结点
while(pa && pb){
if(pa->data <= pb->data){
pc->next = pa;
pc = pa;//移动结点指针至新插入的当前结点
pa = pa->next;
}
else{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
free(*HeadB);
}
|
