数据结构与算法之链表

#include"stdio.h"
#include"malloc.h"

typedef struct
{
    int no;
    int score;
}DataType;

typedef struct node
{
    DataType data;
    struct node *next;
}ListNode;

//线性表的创建  //头插法
ListNode * CreatList()
{
    ListNode *L,*q;
    DataType x;  //x为dataType类型的结构体变量
    L=(ListNode *)malloc(sizeof(ListNode));  //头结点
    L->next=NULL;
    printf("请输入学号和成绩，以学号-1为结束：\n");
    scanf("%d",&x.no);
    while(x.no!=-1)
    {
        scanf("%d",&x.score);
        q=(ListNode *)malloc(sizeof(ListNode));
        q->data=x;
        q->next=L->next;  //头结点所存地址保存于新建结点的指针域中//
        L->next=q;  //新建结点的地址保存于头结点的指针域中
        scanf("%d",&x.no);
    }
    return L;
}
//初始化
ListNode * InitList()
{  
    ListNode *L; 
    L=(ListNode*)malloc(sizeof(ListNode));
    L->next=NULL;
    return L;
}

void PrintList(ListNode * L)
{
    ListNode *p;
    p=L->next;
    while(p!=NULL)
    {
        printf("[%d,%d]\n",p->data.no,p->data.score);
        p=p->next;
    }    
    printf("\n");
}

int GetLength(ListNode *L)
{ 
    int num=0;
    ListNode *p;
    p=L->next;
    while(p!=NULL)
    {  num++;
    p=p->next;
    }
    return(num);
}

void InsertList(ListNode *L,int i,DataType x)
{ 
    ListNode *p,*q,*s;
    int j=1; 
    p=L;
    if(i<1||i>GetLength(L)+1)
        printf("error!\n");
    s=(ListNode *)malloc(sizeof(ListNode));
    s->data=x;
    while(j<=i)
    {   
        q=p;  
        p=p->next;
        j++;
    }    /*找到插入位置*/
    s->next=q->next;//=p
    q->next=s;   
}

//按序号取元素
ListNode *GetNode(ListNode *L,int i)
{ 
    ListNode *p;
    int j=1;
    if(i<1 || i>GetLength(L))
    {
        printf("error!\n");
    }
    p=L->next;
    while(p!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }
       return p;
}
//查找运算
int LocateList(ListNode *L,DataType x)
{ 
    int k=1;
    ListNode *p;
    p=L->next;
    while(p&&p->data.no!=x.no)
    {
        p=p->next;
        k++;
    }
    if(p==NULL) 
        return 0;
    else
        return k;
}
//修改第i个元素
void EditList(ListNode *p,int i,DataType e)
{
    int k=1;
    if(i<1 ||i>GetLength(p))     
    { 
        printf("position error\n");
    }
    while(k<=i)
    {
        p=p->next;
        k++;
    }
    p->data=e;
}

void DeleteList(ListNode *L,int i)
{ 
    ListNode *p,*q;  
    int j=1;
    p=L;
    if(i<1 || i>GetLength(L))
    {
        printf("error!\n");
    }
    while(j<i)
    {
        p=p->next;
        j++;
    }
    q=p->next; 
    p->next=q->next;
    free(q);
}

//排序
void SortList(ListNode *L)
{
    ListNode *p,*q,*pmin;
    DataType e;
    for(p=L->next;p->next!=NULL;p=p->next)  //选择排序
    {
        pmin=p;
        for(q=p->next;q!=NULL;q=q->next)
            if(q->data.score>pmin->data.score)
                pmin=q;
        if(pmin!=p)
        {
            e=p->data;
            p->data=pmin->data;
            pmin->data=e;
        }
    }
}

void main()
{
    ListNode *head,*p;
    DataType e;
    
    //    head=InitList();
    //创建
    head=CreatList();
    PrintList(head);
    
    printf("The length of linklist is %d\n",GetLength(head));
    
    //插入
    e.no=9;  e.score=80;
    InsertList(head,GetLength(head)+1,e);
    printf("插入后：\n");
    PrintList(head);
    printf("The length of linklist is %d\n",GetLength(head));
    //查询     
    e.no=3;
    int k=LocateList(head,e);
    p=GetNode(head,k);
    if(k>0)
        printf("学号为3的记录:[%d %d]\n",p->data.no,p->data.score);
    else
        printf("不存在的\n");
    
    //修改
    e.no=3;  e.score=100;
    int m=LocateList(head,e);
    EditList(head,m,e);
    printf("修改后：\n");
    PrintList(head);
    //删除
    e.no=2;
    int n=LocateList(head,e);
    DeleteList(head,n);
    printf("删除学号为2的记录后：\n");
    PrintList(head);
    printf("The length of linklist is %d\n",GetLength(head));
    //排序
    printf("排序后：\n");
    SortList(head);
    PrintList(head);
}