Ⅰ 求C語言描述的,用線性表的,求交集的演算法
先排序兩個先行表，然後去除重復項。
從一個表(a)第一項開始，為關鍵字掃描另一個表(b)，找一個與其相等的，如果找到，那麼在b表之前的項也不會是a表中的項了，然後從a表下一項作關鍵字，從b表被匹配的元素的下一項開始繼續搜索，如果沒有找到與a中第一項相等的，到遇到比該項大的項時，便從a中下一項開始，重復以上步驟。
排序就不說了，好多種，冒泡，快排，插入，二分插入都行。去除重復項，可以用以下演算法
void StripRepeatElement(int Array[],int Arraylen)
{
int Count = 0;//重復計數器
int i;
for(i = 0;i < ArrayLen;i++)
{
if(Array[i] == Array[i + 1])
{
Count++;
}
else
{
Array[i - Count] = Array[i];
}
}
}
復雜度為O(n)
以下為求交集的演算法，假設兩個表都已經排過序和剔出重復項了
void GetIntersection(int A[],int Alen,int B[],int Blen)
{
int i = 0,j = 0;
while(i < Alen)
{
while(j < Blen)
{
if(A[i] == B[j])
{
//交集
printf(" %d ",A[i]);
j++;
break;
}
else if(A[i] < B[j])
{
//從A的下一項開始匹配
break;
}
else
{
//比較B的下一項
j++;
}
}
i++;
}
}
復雜度也為O(n)
Ⅱ 求大神幫忙用C語言寫一個程序。 要求：定義兩個線性表（內容由用戶輸入），合並這兩個線性表，並按順序
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include <stdbool.h>
typedef struct{
int *data;
int length; // 線性表的長度
int top; // 線性表的當前元素個數
}List;
// 初始化線性表
void list_init(List *li,int length){
li->length = length;
li->top = 0;
li->data = (int*) malloc(li->length * sizeof(int));
}
// 向線性表插入元素
bool add_list(List* li, int data){
if(li->top >= li->length){
return false;
}
li->data[li->top++] = data;
return false;
}
// 將兩個線性表合並並對元素進行排序
void merge_list(List *dest, List *li1, List *li2){
list_init(dest, li1->top+li2->top+1);
// 把線性表li1,li2的所有元素添加到線性表dest中
int i = 0;
while(i < li1->top){
add_list(dest, li1->data[i]);
i++;
}
i = 0;
while(i < li2->top){
add_list(dest, li2->data[i]);
i++;
}
// 把線性表dest元素進行排序(由大到小)
for(i=0; i<dest->top; i++){
int j;
for(j=i; j<dest->top; j++){
if(dest->data[i] < dest->data[j]){
int t = dest->data[i];
dest->data[i] = dest->data[j];
dest->data[j] = t;
}
}
}
}
// 顯示線性表
void show_list(List *li){
int i;
for(i=0; i<li->top; i++){
printf("%3d",li->data[i]);
if((i+1)%10 == 0){
printf("\n");
}
}
printf("\n");
}
int main(void)
{
int arr1[7]={11,4,7,2,9,15,10};
int arr2[5]={2,1,5,1,19};
List li1;
list_init(&li1, 50);
int i;
for(i=0; i<7; i++){
add_list(&li1,arr1[i]);
}
show_list(&li1);
List li2;
list_init(&li2, 50);
for(i=0; i<5; i++){
add_list(&li2,arr2[i]);
}
show_list(&li2);
List dest;
merge_list(&dest, &li1, &li2);
show_list(&dest);
return 0;
}
Ⅲ 幫用C語言弄兩個線性表 謝了 挺簡單的
#include <stdio.h>
#include <stdlib.h>
typedef struct _Lnk
{
int num;
struct _Lnk * next;
}LNK, * PLnk;
int * MallocMem(int num);
void InitLnk(PLnk pHead);
void InitArr(int * pArr, int num);
PLnk GetNiLnk(PLnk lnk);
int * GetNiArr(int * arr, int num);
void ShowLnk(char * pstr, PLnk lnk);
void ShowArr(char * pstr, int * arr, int num);
int main(void)
{
// 初始化原始的鏈表
PLnk pHead = (PLnk)malloc(sizeof(LNK));
printf("現在開始輸入鏈表數據\n");
InitLnk(pHead);
// 初始化原始的順序表
int num=0;
char tmp;
while ((tmp=getchar())!='\n')
{
continue;
}
printf("請輸入元素的個數:\n");
scanf("%d", &num);
//printf("指定的元素個數為：%d\n", num);
int * pArr = NULL;
int * pNiArr = NULL;
if (num>0)
{
pArr = MallocMem(num);
InitArr(pArr, num);
}
PLnk pNiLnk = GetNiLnk(pHead);
if (pArr != NULL)
{
pNiArr = GetNiArr(pArr, num);
}
ShowArr("原始順序表：", pArr, num);
if (pNiArr != NULL)
{
ShowArr("倒置順序表：", pNiArr, num);
}
ShowLnk("原始鏈表：", pHead);
ShowLnk("倒置鏈表：", pNiLnk);
return 0;
}
// subfunctions:
int * MallocMem(int num)
{// 為順序表分配內存
int * pArr = (int *)malloc(sizeof(num));
return pArr;
}
void InitLnk(PLnk pHead)
{// 初始化鏈表的值
int tmp = 0;
printf("請輸入數據：(ctrl+x 結束輸入)\n");
while (scanf("%d", &tmp))
{
PLnk newnode = (PLnk)malloc(sizeof(LNK));
newnode->num = tmp;
pHead->next = newnode;
pHead = newnode;
}
pHead->next = NULL;
return;
}
void InitArr(int * pArr, int num)
{// 初始化順序表的值
for(int i=0; i<num; i++)
{
printf("第 %d 數值= ", i+1);
scanf("%d", &pArr[i]);
}
return;
}
PLnk GetNiLnk(PLnk lnk)
{// 獲得鏈表的倒序
PLnk pNi = (PLnk)malloc(sizeof(LNK));
pNi->next = NULL;
PLnk pHead = pNi, pTmp;
while (lnk = lnk->next)
{
pHead->num = lnk->num;
pTmp = pHead;
pHead = (PLnk)malloc(sizeof(LNK));
pHead->next = pTmp;
}
return pHead;
}
int * GetNiArr(int * arr, int num)
{// 獲取順序表的倒序
int * pNi = MallocMem(num);
for (int i=0; i<num; i++)
{
pNi[i] = arr[num-i-1];
}
return pNi;
}
void ShowLnk(char * pstr, PLnk lnk)
{// 顯示鏈表信息
printf("%s\n", pstr);
int i=0;
while (lnk = lnk->next)
{
printf("%d ", lnk->num);
if ((++i)%5==0)
{
printf("\n");
}
}
printf("\n");
return ;
}
void ShowArr(char * pstr, int * arr, int num)
{// 顯示順序表信息
printf("%s\n", pstr);
for (int i=0; i<num; i++)
{
printf("%d ", arr[i]);
if ((i+1)%5==0)
{
printf("\n");
}
}
printf("\n");
return ;
}
在一個程序裡面了
自己運行了下應該沒什麼問題
但是沒有做內存的釋放等操作， 只是簡單的實現了你說的兩個功能
Ⅳ C語言線性表基本操作求助
#include<stdio.h>
#include<stdlib.h>
# define MAXSIZE 100
# define OK 1
# define ERROR 0
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;
}Sqlist;
int CreateList(Sqlist *L)//創建線性表
{
int i, n, num;
printf("請輸入元素個數：");
scanf("%d", &n);
printf("請依次輸入整數值：");
for (i = 1; i <=n; i++)//一共n個元素,=號
{
scanf("%d", &num);
L->data[i] = num;
L->length++;//長度加1
}
return OK;
}
int ListLength(Sqlist* L)//返回線性表長度
{
printf("線性表的長度為：%d", L->length);
return L->length;
}
int PrintList(Sqlist* L)//依次輸出線性表
{
int i;
for (i = 1; i <= L->length; i++)
{
printf("%d\t", L->data[i]);
}
printf("\n");
return OK;
}
int InsertList(Sqlist *L, int i, ElemType e)//插入元素s
{
int k;
if (L->length == MAXSIZE )
return ERROR;
if (i<1 || i>L->length +1 )
return ERROR;
if (i <= L->length)
{
for (k = L->length; k >= i - 1; k--)//k--，下標從1開始則lengh位置已有元素，不應length-1
L->data[k + 1] = L->data[k];
}
L->data[i] = e;//i不減1
L->length++;
return OK;
}
int DeletList(Sqlist *L, int i)//刪除元素
{
int k;
if (L->length == 0)//==
return ERROR;
if (i<1 || i>L->length)
return ERROR;
if (i <= L->length)
{
for (k = i; k < L->length; k++)
L->data[k] = L->data[k+1];//應該這樣
}
L->length--;
return OK;
}
int GetElem(Sqlist* L, int i, ElemType* e)//用e返回線性表中第i個元素的值
{
if (L->length ==0 || i<1 || i>L->length)//==
return ERROR;
*e = L->data[i];//前面下標都是1開始，就不用-1了
return OK;
}
int MergeList(Sqlist* L1, Sqlist* L2, Sqlist *L3)//兩個線性表求並集，結果放在L3里
{
int i, j, k;
i = 1;
j = 1;
k = 1;
while ((i <= L1->length) && (j <= L2->length))
{
if (L1->data[i] == L2->data[j])
{
L3->data[k] = L1->data[i];
i++;
j++;
}
else
if (L1->data[i] < L2->data[j])
{
L3->data[k] = L1->data[i];
i++;
}
else
{
L3->data[k] = L2->data[j];
j++;
}
k++;
}
if (i > L1->length)
for (i = j; i <= L2->length; i++)
{
L3->data[k] = L2->data[i];
k++;
}
else
for (j = i; j <= L1->length; j++)
{
L3->data[k] = L1->data[j];
k++;
}
L3->length = k - 1;
return OK;
}
void menu()
{
printf("\n");
printf(" *******************順序線性表功能菜單*******************\n");
printf(" * 1：建立線性表 2：插入元素 *\n");
printf(" * 3: 刪除元素 4：合並線性表 *\n");
printf(" * 5：列印線性表 6：查找特定元素 *\n");
printf(" * 7：線性表長度 8：退出 *\n");
printf(" ********************************************************\n");
printf(" 請輸入你的選擇：");
}
void main()
{
Sqlist L, L1, L2, L3;
ElemType e;
int i,n,flag;
char a;
L.length = 0;
//int CreateList(Sqlist *L);//函數原型
//int ListLength(Sqlist* L);
//int PrintList(Sqlist* L);
//int InsertList(Sqlist *L, int i, ElemType e);
//int DeletList(Sqlist *L, int i);
//int GetElem(Sqlist* L, int i, ElemType e);
//int MergeList(Sqlist L1, Sqlist L2, Sqlist *L3);
menu();
do
{
scanf("%d",&n);
if(n>=1&&n<=7)
{
flag=1;
break;
}
else
{
flag=0;
printf("您輸入有誤，請重新選擇!");
}
}
while(flag==0);
while(flag==1)
{
switch (n)
{
case 1:
CreateList(&L);
PrintList(&L);
break;
case 2:
printf(" 請輸入要插入的數據元素：");
scanf("%d", &e);
printf(" 請輸入要插入的元素位置：");
scanf("%d", &i);
InsertList(&L, i, e);
break;
case 3:
printf(" 請輸入要刪除的元素位置：");
scanf("%d", &i);
DeletList(&L, i);
PrintList(&L);
break;
case 4:
printf(" 創建第一個順序表");
CreateList(&L1);
printf(" 創建第二個順序表");
CreateList(&L2);
PrintList(&L1);
PrintList(&L2);
MergeList(&L1, &L2, &L3);
PrintList(&L3);
break;
case 5:
PrintList(&L);break;//這里開始都忘了break
case 6:
printf("請輸入查看元素序號：");
scanf("%d", &i);
GetElem(&L, i, &e);
printf("第%d個元素為%d", i, e);break;
case 7:
ListLength(&L);break;
case 8:
exit(0);
break;
default:
break;
}
getchar();
printf("\n");
printf("是否繼續進行(y or n):\n");
scanf("%c",&a);
if(a=='y')
{
flag=1;
system("cls"); /*清屏*/
menu(); /*調用菜單函數*/
printf("請再次選擇你需要操作的步驟(1--7):\n");
scanf("%d",&n);
printf("\n");
}
else
exit(0);
}
}