Impl:LinkListBasedSort - 编程开发

#include<stdio.h>#include<stdlib.h>#include"LinkList.h"//创建单链表void CreateList(LinkList L,DataType a[],int n){int i;for(i=1;i<=n;i++)InsertList(L,i,a[i-1]);}//用链表实现选择排序。将链表分为两段，p指向应经排序的链表部分，q指向未排序的链表部分void SelectSort(LinkList L){ListNode *p,*q,*t,*s;p=L;while(p->next->next!=NULL){//用q指针进行遍历链表for(s=p,q=p->next;q->next!=NULL;q=q->next)if(q->next->data<s->next->data)s=q;//如果q指针指向的元素值小于s指向的元素值，则s=qif(s!=q){//如果*s不是最后一个结点，则将s指向的结点链接到p指向的链表后面t=s->next;//将结点*t从q指向的链表中取出s->next=t->next;t->next=p->next;//将结点*t插入到p指向的链表中p->next=t;}p=p->next;}}void main_Select(){LinkList L,p;int n=8;DataType a[]={45,67,21,98,12,39,81,53};InitList(&L);CreateList(L,a,n);printf("排序前：\n");for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");SelectSort(L);printf("排序后：\n");for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");system("pause");}//链表的插入排序void InsertSort(LinkList L){ListNode *p=L->next;ListNode *pre,*q;L->next=NULL;//初始时，已排序链表为空while(p!=NULL){//p是指向待排序的结点if(L->next==NULL){//如果*p是第一个结点，则插入到L，并令已排序的最后一个结点的指针域为空L->next=p;p=p->next;L->next->next=NULL;}else{//p指向待排序的结点，在L指向的已经排好序的链表中查找插入位置pre=L;q=L->next;while(q!=NULL&&q->data<p->data){//在q指向的有序表中寻找插入位置pre=q;q=q->next;}q=p->next;//q指向p的下一个结点，保存待排序的指针位置p->next=pre->next;//将结点*p插入到结点*pre的后面pre->next=p;//p指向下一个待排序的结点p=q;}}}void main_Insert(){LinkList L,p;int n=8;DataType a[]={87,34,22,93,102,56,39,21};InitList(&L);CreateList(L,a,n);printf("排序前：\n");for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");InsertSort(L);printf("排序后：\n");for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");system("pause");}void main(){main_Select();main_Insert();}//单链表#pragma once#include<stdio.h>#include<stdlib.h>typedef int DataType;typedef struct Node{DataType data;//数据域struct Node *next;//指针域}ListNode,*LinkList;//将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空void InitList(LinkList *head){if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)exit(-1);(*head)->next=NULL;}//判断单链表是否为空，就是通过判断头结点的指针域是否为空int ListEmpty(LinkList head){if(head->next==NULL)return 1;elsereturn 0;}//查找单链表中第i个结点。查找成功返回该结点的指针表示成功；否则返回NULL表示失败ListNode *Get(LinkList head,int i){ListNode *p;int j;if(ListEmpty(head))return NULL;if(i<1)return NULL;j=0;p=head;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)return p;elsereturn NULL;}//查找线性表中元素值为e的元素，查找成功将对应元素的结点指针返回，否则返回NULL表示失败ListNode *LocateElem(LinkList head,DataType e){ListNode *p;p=head->next;while(p){if(p->data!=e)p=p->next;elsebreak;}return p;}//查找线性表中元素值为e的元素，查找成功将对应元素的序号返回，否则返回0表示失败int LocatePos(LinkList head,DataType e){ListNode *p;int i;if(ListEmpty(head))return 0;p=head->next;i=1;while(p){if(p->data==e)return i;else{p=p->next;i++;}}if(!p)return 0;}//在单链表中第i个位置插入一个结点，结点的元素值为e。插入成功返回1，失败返回int InsertList(LinkList head,int i,DataType e){ListNode *p,*pre;int j;pre=head;j=0;while(pre->next!=NULL&&j<i-1){pre=pre->next;j++;}if(!pre){printf("wrong place\n");return 0;}if((p=(LinkList)malloc(sizeof(ListNode)))==NULL)exit(-1);p->data=e;p->next=pre->next;pre->next=p;return 1;}//删除单链表中的第i个位置的结点。删除成功返回1，失败返回0int DeleteList(LinkList head,int i,DataType *e){ListNode *pre,*p;int j;pre=head;j=0;while(p->next!=NULL&&pre->next->next!=NULL&&j<i-1){pre=pre->next;j++;}if(j!=i-1){printf("delete wrong place\n");return 0;}p=pre->next;pre->next=p->next;free(p);return 1;}int ListLength(LinkList head){ListNode *p;int count=0;p=head;while(p->next!=NULL){p=p->next;count++;}return count;}void DestroyList(LinkList head){ListNode *p,*q;p=head;while(p!=NULL){q=p;p=p->next;free(q);}}

去陌生的街角，去做一切我们曾经或现在也很想做的事情，

相关文章：

你感兴趣的文章：

标签云：