線性表的順序表示和實作
①集合A=AUB,無序的;
②A,B兩個順序表遞增有序,執行C=AUB,算法時間複雜度要求為 O(n+m)(A,B這兩個順序表隻允許周遊一次);
③//實作順序表的就地逆置,即利用原表的存儲空間将線性表(a1,...,an)逆置為(an,...,a1);
④//設A=(a1,...,an)和B=(b1,...,bn)均為順序表。試寫一個比較 A,B 大小的算法,依次比較 A,B 元素的值,如果一樣則繼續比較,如果不一樣則比較完成。;
⑤//設順序表va中的資料元素遞增有序。試寫一算法,将x插入到順序表的适當位置上,以 保持該表的有序性;
⑥已知 A,B 和 C 為三個遞增有序的順序表,現要求對 A 表作如下操作:
删去那些既在 B 表中出現又在 C 表中出現的元素。
試對順序表編寫實作上述操作的算法,并分析你的算法的 時間複雜度(注意:題中沒有特别指明同一表中的元素值各不相同)。
頭檔案
#pragma once//防止頭檔案被重複引用
//動态不定長順序表
#define INIT_SIZE 10//順序表的初始化大小
typedef struct SqList
{
int *elem;//指向動态記憶體建立的記憶體,用于存儲資料
int length;//存放有效資料個數
int listsize;//存放順序表的總大小
}Sqlist,* PSqList;//PSqList為結構體類型指針
//初始化線性表
void InitSqlist(PSqList ps);
//在ps的pos位置處插入資料val
bool Insert(PSqList ps,int pos,int val);
//在ps中查找第一個key值,找到傳回下标,失敗傳回-1
int Search(PSqList ps,int key);
//删除ps中的第一個key值
bool DeleteVal(PSqList ps,int key);
//删除ps中pos位置的值
bool DeletePosVal(PSqList ps,int pos);
//擷取ps中pos位置的值
int GetElel(PSqList ps,int pos);
//将ps中pos位置的值設為newpos
bool SetElem(PSqList ps,int pos,int newval);
//擷取有效資料個數
int GetLentgh(PSqList ps);
//判斷ps是否為空
bool IsEmpty(PSqList ps);
//輸出ps
void Show(PSqList ps);
//清空ps
void Clear(PSqList ps);
//銷毀ps
void Destory(PSqList ps);
函數說明以及實作與順序線性表的實作:
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"SeqList.h"//引用本項目頭檔案
//初始化線性表
void InitSqlist(PSqList ps)
{
assert(ps != NULL);
if(ps == NULL)
{
printf("Init Error\n");
return;
}
//-> 自帶 *
ps->elem = (int*)malloc(sizeof(int)*INIT_SIZE);//存放整型元素
ps->length = 0;//初始化長度為0
ps->listsize = INIT_SIZE;
}
//擴容,将總容量擴大為原來的2倍
static void Inc(PSqList ps)
{
assert(ps != NULL);
if(ps == NULL)
{
return;
}
ps->elem = (int*)realloc(ps->elem,sizeof(int)*INIT_SIZE*2);//realloc會把原來資料copy過來
ps->listsize *= 2;
}
//判斷ps是否已滿,内部函數,不對外
static bool IsFull(PSqList ps)
{
assert(ps != NULL);
if(ps == NULL)
{
return false;
}
return ps->length == ps->listsize;//已滿
}
//在ps的pos位置處插入資料val
//插入的資料必須在順序表的最左邊,且連續
bool Insert(PSqList ps,int pos,int val)//O(n)
{
assert(ps != NULL);
assert(ps != NULL);
if(ps == NULL || pos < 0 || pos > ps->length)
{
return false;
}
if(IsFull(ps))
{
Inc(ps);//如果滿了,就擴容
}
for(int i = ps->length - 1;i >= pos;i--)
{
ps->elem[i+1] = ps->elem[i];
}
ps->elem[pos] = val;
ps->length++;
return true;
}
//在ps中查找第一個key值,找到傳回下标,失敗傳回-1
int Search(PSqList ps,int key)
{
assert(ps != NULL);
if(ps == NULL)
{
return false;
}
int flag = -1;
for(int i=0;i < ps->length;i++)
{
if(ps->elem[i] == key)
{
flag = i; //找到了
break;
}
}
return flag;
}
//删除ps中的第一個key值
bool DeleteVal(PSqList ps,int key)
{
assert(ps != NULL);
if(ps == NULL)
{
return false;
}
int index = Search(ps,key);
return DeletePosVal(ps,index);
}
//删除ps中pos位置的值
bool DeletePosVal(PSqList ps,int pos)
{
assert(ps != NULL);
if(ps == NULL || pos > ps->length && pos < 0)
{
return false;
}
for(int i = pos;i + 1 < ps->length;i++)//将後面的資料往前移
{
ps->elem[i]=ps->elem[i+1];
}
ps->length --;
return true;
}
//擷取ps中pos位置的值
int GetElel(PSqList ps,int pos)
{
assert(ps != NULL );
if(ps == NULL && pos > ps->length && pos < 0 )
{
return -1;
}
return ps->elem[pos];
}
//将ps中pos位置的值設為newpos
bool SetElem(PSqList ps,int pos,int newval)
{
assert(ps != NULL );
if(ps == NULL && pos > ps->length && pos < 0 )
{
return false;
}
ps->elem[pos] = newval;
return true;
}
//擷取有效資料個數
int GetLentgh(PSqList ps)
{
assert(ps != NULL );
if(ps == NULL)
{
return 0;
}
return ps->length;
}
//判斷ps是否為空
bool IsEmpty(PSqList ps)
{
assert(ps != NULL );
if(ps == NULL)
{
return false;
}
return ps->length == 0;
}
//輸出ps
void Show(PSqList ps)
{
assert(ps != NULL );
if(ps == NULL && ps->length < 0)
{
return ;
}
for(int i = 0;i < ps->length;i++)
{
printf("%d ",ps->elem[i]);
}
printf("\n");
}
//清除資料
void Clear(PSqList ps)
{
assert(ps != NULL );
if(ps == NULL)
{
return ;
}
ps->length = 0;
}
//銷毀ps,回收記憶體
void Destory(PSqList ps)
{
assert(ps != NULL );
if(ps == NULL)
{
return ;
}
free(ps->elem);
ps->elem = NULL;
ps->length = 0;
ps->listsize = 0;
}
主函數(所有函數都已經測試過):
#include<stdio.h>
#include"SeqList.h"
//集合A=AUB,無序的
void Union_unsort(PSqList pA,PSqList pB)
{
int value_a = 0;
int Lenght_A = GetLentgh(pA);
int Lenght_B = GetLentgh(pB);
for(int i = 0;i < Lenght_B;i++)
{
value_a = GetElel(pB,i);
if(-1 == Search(pA,value_a))
{
Insert(pA,Lenght_A,value_a);
}
}
printf("\n");
}
//A,B兩個順序表遞增有序,執行C=AUB,算法時間複雜度要求為 O(n+m)(A,B這兩個順序表隻允許周遊一次)
void Union_Merge_sort(PSqList pA,PSqList pB,PSqList pC)
{
int value_a = 0,value_b = 0;
int Lenght_A = GetLentgh(pA);
int Lenght_B = GetLentgh(pB);
int i = 0,j = 0,k = 0;
while (i < Lenght_A && j < Lenght_B)
{
value_a = GetElel(pA,i);
value_b = GetElel(pB,j);
if(value_a < value_b)
{
Insert(pC,k,value_a);
i++;
}
else if(value_a == value_b)
{
Insert(pC,k,value_a);
i++;
j++;
}
else
{
Insert(pC,k,value_b);
j++;
}
k++;
}
//一個順序表長度>另一個順序表長度
while (i < Lenght_A)
{
value_a = GetElel(pA,i);
Insert(pC,k,value_a);
i++,k++;
}
while (j < Lenght_B)
{
value_b = GetElel(pB,j);
Insert(pC,k,value_b);
j++,k++;
}
}
void Swap_Int(int *a,int *b)
{
int tmp = 0;
tmp = *a;
*a = *b;
*b = tmp;
}
//實作順序表的就地逆置,即利用原表的存儲空間将線性表(a1,...,an)逆置為(an,...,a1)。
void Inversion(PSqList pA)
{
int tmp = 0;
int length_A = GetLentgh(pA);
for(int i = 0,j = length_A - 1;i < length_A / 2;i++,j--)
{
Swap_Int(&pA->elem[i],&pA->elem[j]);
}
}
int Min_Int(int a,int b)
{
return a < b ? a : b;
}
//設A=(a1,...,an)和B=(b1,...,bn)均為順序表。試寫一個比較 A,B 大小的算法,依次比較 A,B 元素的值,如果一樣則繼續比較,如果不一樣則比較完成。
int Compare(PSqList pA,PSqList pB)
{
int Lenght_A=GetLentgh(pA);
int Lenght_B=GetLentgh(pB);
for(int i = 0;i < Min_Int(Lenght_A,Lenght_B);i++)
{
if(GetElel(pA,i) != GetElel(pB,i))
{
return GetElel(pA,i) - GetElel(pB,i);//不相等傳回較大的順序表
}
}
return Lenght_A - Lenght_B;//==0表示相等,大于0A大,反之B大
}
//設順序表va中的資料元素遞增有序。試寫一算法,将x插入到順序表的适當位置上,以保持該表的有序性。
int Insert_Merge_SList(PSqList pA,int x)
{
int i = 0;
for(i = GetLentgh(pA) - 1;i >= 0;i--)
{
if(x >= GetElel(pA,i))
{
break;
}
}
return Insert(pA,i + 1,x);
}
/*
已知 A,B 和 C 為三個遞增有序的順序表,現要求對 A 表作如下操作:
删去那些既在 B 表中出現又在 C 表中出現的元素。
試對順序表編寫實作上述操作的算法,并分析你的算法的 時間複雜度(注意:題中沒有特别指明同一表中的元素值各不相同)。
*/
void List_A_sub_BC(PSqList pA,PSqList pB,PSqList pC)//O(n)
{
int value_a = 0,value_b = 0,value_c = 0;
int i = 0,j = 0,k = 0;//分别為順序表ABC的下标
while (i < GetLentgh(pA) && j < GetLentgh(pB) && k < GetLentgh(pC))
{
value_a = GetElel(pA,i);
value_b = GetElel(pB,j);
value_c = GetElel(pC,k);
if( value_a == value_b && value_a == value_c )
{
DeletePosVal(pA,i);
}
else if(value_b < value_a )
{
j++;
}
else if(value_c < value_a )
{
k++;
}
else
{
i++;
}
}
printf("\n");
}
int main()
{
SqList pA,pB,pC;
InitSqlist(&pA);
InitSqlist(&pB);
InitSqlist(&pC);
Insert(&pA,0,1);Insert(&pA,1,2);
Insert(&pA,2,3);Insert(&pA,3,5);
Insert(&pA,4,7);Insert(&pA,5,9);
Insert(&pA,6,10);Insert(&pA,7,11);
Insert(&pA,8,19);Insert(&pA,9,29);
Insert(&pB,0,1);Insert(&pB,1,3);
Insert(&pB,2,4);Insert(&pB,3,6);
Insert(&pB,4,8);
Insert(&pC,0,1);Insert(&pC,1,3);
Insert(&pC,2,5);Insert(&pC,3,6);
Insert(&pC,4,8);Insert(&pC,5,9);
printf("A集合:");
Show(&pA);
printf("B集合:");
Show(&pB);
printf("C集合:");
Show(&pC);
Destory(&pA);
Destory(&pB);
Destory(&pC);
return 0;
}