查找和排序是两种很基本的操作。今天我们先用直接插入排序对输入的链表进行排序，然后利用折半查找进行对给定key值的查找。这里我们只是实现了对链表的折半查找，折半查找的ASL=lg(n+1)-1,折半查找对于有序表、顺序存储结构有很高的查找效率，但对于链表则无法进行有效的折半查找（需要随时进行元素的定位以及指针定位，例如代码的GetPoint()和GetElem()函数）.另外利用尾插法建立的链表是逆序的,为了方便需要逆置.(欢迎学习交流新浪微博ID:@小玩多)
以下代码在Win-Tc1.9.1下编译通过.
#include "stdio.h"
#include "malloc.h"
//节点的声明
typedef struct Node{
int data;
struct Node * next;
}node,*ptrNode;
//采用尾插法建立单链表
ptrNode Create_List(int n){//参数n为链表的节点数
int i =0;
ptrNode p,head;
head = (ptrNode)malloc(sizeof(node));
head->next = NULL;
for(i=n;i>0;i--){
p = (ptrNode)malloc(sizeof(node));
printf("input the value:");
scanf("%d",&p->data);//注意此处的&
p->next = head->next;//使新节点和后一节点连接起来
head->next = p;//使新的节点和头节点连接起来，保证head的指针域存储的是下一节点的地址
}
return head;
}
//打印单链表,采用尾插法建立链表后打印是逆序打印的
void Print_List(ptrNode head){
ptrNode p;
p = head->next;
while(p){
printf("[%d] ",p->data);//打印当前数据
p=p->next;//指针后移
}
}
//取得链表第i个元素
int GetElem(ptrNode head,int i){
int j=0;
ptrNode p;
p = head;
while(p&&j<i){
p = p->next;
j++;
}
return p->data;
}
//取得链表第i个元素的指针
ptrNode GetPoint(ptrNode head,int i){
int j=0;
ptrNode p;
p = head;
while(p&&j<i){
p = p->next;
j++;
}
return p;
}
//单链表的折半查找
ptrNode Search_Bin(ptrNode head,int key,int length){
int low = 1,high = length,mid = 0;
while(low<=high){
mid = (low+high)/2;
if(key==GetElem(head,mid))return GetPoint(head,mid);
else if(key<GetElem(head,mid)) high = mid-1;
else low = mid+1;
}
return NULL;
}
//单链表的就地逆置
ptrNode Opposite_List(ptrNode head){
ptrNode p,p_next,r;
p=r=NULL;
p = head->next;
while(p){
p_next = p->next;
p->next = r;//逆置连接
r = p;
p = p_next;
}
head->next = r;
return head;
}
//单链表的直接插入排序
ptrNode Insert_Sort(ptrNode head,int length){
int i,j,temp;
ptrNode p;
for(i=2;i<=length;i++){
temp = GetElem(head,i);
j = i-1;
while(j>=1&&(temp<GetElem(head,j))){
p = GetPoint(head,j);
p->next->data = p->data;
j--;
}
(GetPoint(head,j+1))->data = temp;
}
return head;
}
void main(){
ptrNode L,value;
L= Create_List(5);
Print_List(L);
L = Opposite_List(L);//对利用尾插法的单链表进行逆置
printf("\n");
Print_List(L);
value = Search_Bin(L,7,5);
printf("value = %d",value->data);
getch();
}
加载中…
喜欢