/*

源文件名：P1.cpp

功能：順序表操作

*/

#include <conio.h>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#include <iostream>

#define max 10000

struct SqList

{

int data[max];? ? ? ? ?//存放元素的數(shù)組

int length;? ? ? ? ? ? //當(dāng)前長度

};

void init(SqList &list);

void display(SqList &list);

void insert(SqList &list,int,int);

void search(SqList &list,int);

void del(SqList &list,int);

void simpleSort(SqList &list);

void binarySearch(SqList &list,int);

void nzlist(SqList &list);

SqList list;

int main()

{

char choice;

int key;

while (1)

{

system("cls");

printf("? ? ?學(xué)號: ****? ? ?姓名：***? ? ? ? ? ? \n ");?

printf("\n\n\n\n");? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

printf("\t\t? ? ? ? ? ? ?順序表操作? \n");

printf("\t\t======================================");

printf("\n\n");

printf("\t\t? ? ? ? ? ? ?1：初始化? ? ? ?\n");

printf("\t\t? ? ? ? ? ? ?2：顯示? ? ? ? ?\n");

printf("\t\t? ? ? ? ? ? ?3：單個插入? ? ?\n");

printf("\t\t? ? ? ? ? ? ?4：查找? ? ? ? ?\n");

printf("\t\t? ? ? ? ? ? ?5：刪除? ? ? ? ?\n");

printf("\t\t? ? ? ? ? ? ?6：簡單選擇排序 \n");

printf("\t\t? ? ? ? ? ? ?7：折半查找? ? ?\n");

printf("\t\t? ? ? ? ? ? ?8：逆置線性表? ?\n");

printf("\n");

printf("\t\t? ? ? ? ? ? ?0：退出? ? ? ? ?\n");

printf("\n");

printf("\t\t請選擇：");

choice = getch();

system("cls");

switch(choice)

{

case '1':

void init(SqList &list);

break;

case '2':

void display(SqList &list);

break;

case '3':

int wz; //在wz出插入key

void insert(SqList &list,int,int);

break;

case '4':

printf("輸入你要查找到值(數(shù)字)\n" );

? ? ? ? ? ? scanf("%d",&key);

void search(SqList &list,int);

break;

case '5':

printf("輸入你要刪除的值(數(shù)字)\n" );

? ? ? ? ? ? scanf("%d",&key);

void del(SqList &list,int);

break;

case '6':

void simpleSort(SqList &list);

break;

case '7':

? ? ? ? ? ? ? ? printf("輸入你要二分查找的值(數(shù)字)\n" );

? ? ? ? ? ? scanf("%d",&key);

? ? void binarySearch(SqList &list,int);

break;

case '8':

? ? ? ? ? ? ? ? void nzlist(SqList &list);

break;

case '0':

exit(0);

}

}

return 0;

}

//屏幕提示后，從鍵盤輸入線性表長度和隨機(jī)數(shù)種子，生成指定長度的線性表list

void init(SqList &list)

{

int i;

while (1)

{

printf("輸入元素個數(shù)（0 － %d ）：\n",max);

scanf("%d",&list.length);

if (list.length >= 0 && list.length <= max)

break;

printf("\n");

}

while (1)

{ ? ??

printf("輸入隨機(jī)數(shù)種子（0－32767）：\n");

scanf("%d",&i);

if (i >= 0 && i <= 32767)

break;

printf("\n");

}

srand(i);? //指定隨機(jī)數(shù)種子，相同的種子將產(chǎn)生相同的數(shù)據(jù)序列

rand();

for (i = 0; i < list.length; i++)

{

list.data[i] = rand() % 10000;

}

for (i = list.length; i < max; i++)

list.data[i] = 0;

}

// 注意：部分算法的函數(shù)定義如下，其他需自行不全?

//1.在屏幕上依次顯示線性表list中的元素個數(shù)和全部元素

void display(SqList &list)

{int i;

for(i=0;i<list.length;i++)

{printf("[%5d]= %6d\n",(i+1),list.data[i]);}

puts("press 1 to continue");

? ?while(scanf("%d",&i )!=1);

}

//2.屏幕提示后，從鍵盤輸入需要插入的位置wz和元素值key

void insert(SqList &list,int wz,int key)

{

SqList *L;

printf("輸入要插入元素的位置:\n");

scanf("%d",&wz);

printf("輸入要插入的數(shù)據(jù)元素的值:\n");

scanf("%d",&key);

if(wz<1||wz>L->length+1){

printf("輸入的位置不在范圍內(nèi)！\n");

}

wz--;

int j;

for (j=L->length;j>wz;j--)

? ? list.data[j]=list.data[j-1];

list.data[wz]=key;

L->length++;

? ? puts("press 1 to continue");

? ? while(scanf("%d",&wz )!=1);

??

}

//3.屏幕提示后，在線性表list中搜索這個元素key，若存在該元素，則給出位置信息，

//? 否則，顯示“不存在此數(shù)！”

//屏幕顯示搜索結(jié)果和搜索過程中的比較次數(shù)

void search(SqList &list,int key)

{?

int i;

int flag=0;

for(i=0;i<list.length;i++){

if(list.data[i]==key)break;

flag++;

}

if( (i==list.length)&&(list.data[i]!=key)) printf("不存在此數(shù)！\n" );

else printf("[%5d]= %6d\n",(i+1),list.data[i]);

printf("查找次數(shù):%d\n",flag );

puts("press 1 to continue");

while(scanf("%d",&i )!=1);

}

//4.屏幕提示后，在線性表list中刪除這個元素key，并顯示相關(guān)信息

//屏幕顯示刪除成功與否的信息，并顯示比較次數(shù)和移動次數(shù)

void del(SqList &list,int key)

{

?int i;

? ? ?int flag=0;

for(i=0;i<list.length;i++){

if(list.data[i]==key)break;

flag++;

}

if( (i==list.length)&&(list.data[i]!=key)) printf("不存在此數(shù)！\n" );//查找?

else {

printf("[%5d]= %6d\n",(i+1),list.data[i]);

for(i=0;(i+1)<list.length;i++){

list.data[i]=list.data[i+1];

}

list.length--;

printf("刪除成功!\n" );

}

puts("press 1 to continue");

while(scanf("%d",&i )!=1);

}

//5.編程實現(xiàn)一個順序表的就地逆置，即利用原表的存儲空間將順序表逆置。

void nzlist(SqList &list)

{

? int i;

for(i=0;i<list.length/2;i++){

list.data[i] += list.data[list.length-i-1];//i是總和

list.data[list.length-i-1] = list.data[i]-list.data[list.length-i-1];//尾部變成原來的i

list.data[i] -= list.data[list.length-i-1];//頭部變成原來的list.data[list.length-i-1]

}

for(i=0;i<20;i++)

? ? printf("就地逆置完成！? ");

}

//其他函數(shù)實現(xiàn)，請自行補(bǔ)充?

//6.簡單選擇排序?

void simpleSort(SqList &list)

{

int i,j,times=0,swaps=0,t;

printf("排序如下:\n" );

for(i=0;i<list.length;i++)

? {for(j=i;j<list.length;j++){

? ? times++;

? ? if(list.data[i]>list.data[j]){

? ? ? swaps++;

? t=list.data[i];

? ? ? list.data[i]=list.data[j];

? ? ? list.data[j]=t;

? ? }

? }}

?

? printf("比較次數(shù):%d\n移動次數(shù):%d",times,swaps );

? puts("press 1 to continue");

? while(scanf("%d",&i )!=1);

?}?

?//7.折半查找?

?void binarySearch(SqList &list,int key)

?{

? int times=0;

? int mid,low=0,high=list.length-1;

?

? ? while(low<=high){

? ? times++;

? ? ? if(list.data[low]==key){

? ? ? ? printf("[%d]%d,查找次數(shù)為:%d",low,list.data[low],times );

? ? ? ? break;}

? ? ? if(list.data[high]==key){

? ? ? ? printf("[%d]%d,查找次數(shù)為:%d",high,list.data[high],times );

? ? ? ? break;

? ? ? }

? ? mid=(low+high)/2;

? ? if(list.data[mid]==key){

? ? ? printf("[%d]%d,查找次數(shù)為:%d",mid,list.data[mid],times );

? ? ? break;

? ? }

? ? if(list.data[mid]>key)high=mid-1;

? ? if(list.data[mid]<key)low=mid+1;

? ? }

? ? if(low>high)printf("沒有找到,查找次數(shù)為:%d\n",times );

int i;

? ? puts("press 1 to continue");

while(scanf("%d",&i )!=1);

}