typedef struct LNode
{
int data
struct LNode *next
} LNode, *LinkList
LinkList List_TailInsert(LinkList L)
{
int x//设元素类型为整型
L = (LinkList)malloc(sizeof(LNode))
LNode *s, *r = L//r为表尾指针
printf("请输入表元素(以999结尾)：")
scanf("%d", &x)//输入结点的值
while (x != 999) //输入999表示结束
{
s = (LNode *)malloc(sizeof(LNode))
s->data = x
r->next = s
r = s//r指向新的表尾结点
scanf("%d", &x)
}
r->next = NULL//尾结点指针置空
return L
}
void print(LinkList L)
{
while (L->next != NULL)
{
L = L->next
printf("%d ", L->data)
}
}
LNode *LocateElem(LinkList L, int e)
{
int i = 1
LNode *p = L->next //头结点赋给p
while (p != NULL &&p->data != e) //从第1个结点开始找data值为e的结点
{
p = p->next
i++
}
return p//找到后返回该结点指针，否则返回NULL
}
int main()
{
LinkList L, A
LNode *p
int e, i
A = (LinkList)malloc(sizeof(LNode))
A = List_TailInsert(L)
printf("尾插法建立的单链表：")
print(A)
printf("\n")
printf("请输入要查找的值：")
scanf("%d", &e)
p = LocateElem(A, e)
printf("要查找的值%d的地址为%p.", e, p)
printf("\n")
return 0
}
#include<stdio.h>#include<stdlib.h>
#define N 10
void shellpass(int a[], int n, int d)
{
int i,j,temp
for(i=di<ni++)
{
if(a[i]<a[i-d])
{
temp=a[i]
for(j=i-dj>=0&&temp<a[j]j-=d)
a[j+d]=a[j]
a[j+d]=temp
}
}
}
void shellsort(int a[], int n, int delta[], int t)
{
int i, j
for(i=0 i<t i++)
{
shellpass(a, n, delta[i])
printf("第%d趟希尔排序，增量为%d，排序之后的结果\n",i+1,delta[i])
for(j=0 j<n j++)
{
printf("%d\t",a[j])
}
printf("\n")
}
}
void main()
{
int n=N, a[N]
int b[3] = {5,3,1}
int i
printf("输入%d个数\n", n)
for(i=0i<ni++)
{
printf("第%d个数:\t",i+1)
scanf("%d",&a[i])
}
shellsort(a, n, b, 3)
printf("最终希尔排序之后的结果\n")
for(i=0i<ni++)
{
printf("%d\t",a[i])
}
printf("\n")
}
关键字序列是{22,41,53,8,46,30,1,31,66}, 计算过程如下:插入关键字22, 索引(散列值) = 3*22 mod 11 = 0, 存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22
插入关键字41, 索引(散列值) = 3*41 mod 11 = 2, 存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 41
插入关键字53, 索引(散列值) = 3*53 mod 11 = 5, 存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 41 53
插入关键字8, 索引(散列值) = 3*8 mod 11 = 2, 有冲突,取索引2+1=3,没有冲突,存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 41 8 53
插入关键字46, 索引(散列值) = 3*46 mod 11 = 6, 存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 41 8 53 46
插入关键字30, 索引(散列值) = 3*30 mod 11 = 2, 有冲突,取索引2+1=3,仍有冲突,
取索引3+1=4,没有冲突,存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 41 8 30 53 46
插入关键字1, 索引(散列值) = 3*1 mod 11 = 3, 有冲突,依次取索引4,5,6,均有冲突,
取索引7,没有冲突,存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 41 8 30 53 46 1
插入关键字31, 索引(散列值) = 3*31 mod 11 = 5, 有冲突,依次取索引6,7,均有冲突,
取索引8,没有冲突,存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 41 8 30 53 46 1 31
插入关键字66, 索引(散列值) = 3*66 mod 11 = 0, 有冲突,取索引0+1=1,没有冲突,存入散列表:
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 22 66 41 8 30 53 46 1 31
这就是最后得到的散列表.
//C语言测试程序
#include<stdio.h>
#include<stdlib.h>
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 11
#define NULLKEY -1
typedef int Status
typedef struct
{
int *elem
int count
}HashTable
int m=0
Status InitHashTable(HashTable *H)
{
int i
m=HASHSIZE
H->count=m
H->elem=(int *)malloc(m*sizeof(int))
for(i=0i<mi++)
{
H->elem[i]=NULLKEY
}
return SUCCESS
}
int Hash(int key)
{
return (3*key) % m
}
void InsertHash(HashTable *H,int key)
{
int addr
int pos
pos=Hash(key)
addr=pos
while(H->elem[addr] != NULLKEY)
{
////////
printf("索引=%d 有冲突.\n",addr)
////////
addr = (addr+1) % m
if(addr==pos)
{
printf("\n散列表已满!\n")
exit(1)
}
}
H->elem[addr]=key
}
Status SearchHash(HashTable H,int key,int *addr)
{
*addr = Hash(key)
while(H.elem[*addr] != key)
{
*addr = (*addr+1) % m
if(H.elem[*addr]==NULLKEY || *addr==Hash(key))
{
return UNSUCCESS
}
}
return SUCCESS
}
void showHashTable(HashTable *H)
{
int i
for(i=0 i < H->count i++)
{
printf("%4d",i)
}
printf("\n")
for(i=0 i < H->count i++)
{
if(H->elem[i]==NULLKEY)
{
printf("%4c",0x20)
}
else
{
printf("%4d",H->elem[i])
}
}
printf("\n")
}
int main()
{
int key[]={22,41,53,8,46,30,1,31,66}
int len
int i
HashTable H
InitHashTable(&H)
len=sizeof(key)/sizeof(key[0])
for(i=0i<leni++)
{
printf("插入关键字 %d, 索引(Hash) = %d\n",key[i],Hash(key[i]))
InsertHash(&H,key[i])
showHashTable(&H)
}
return 0
}
