① 跪求分別寫一個線性表的插入的完整演算法
//Try:
#include<iostream>
#include<stdlib.h>
usingnamespacestd;
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;//Status是函數的類型,其值是函數結果狀態碼
typedefintElemType;//ElemType為數據元素,暫定為int型
#defineLIST_INIT_SIZE100//線性表存儲空間的初始分配量
#defineLIST_INCREMENT10//線性表存儲空間的分配增量
typedefstruct//線性表順序存儲結構
{
ElemType*elem;//存儲空間基址
intlength;//線性表當前長度
intlistsize;//當前分配的存儲容量(以sizeof(ElemType)為單位)
}SqList;
StatusInitList_SL(SqList&L)//初始化順序線性表
{
//構造一個空的線性表L
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);//存儲分配失敗
L.length=0;//空表長度為0
L.listsize=LIST_INIT_SIZE;//初始存儲容量
returnOK;
}
Statusvisit(ElemTypee)//訪問元素
{
cout<<e<<"";
returnOK;
}
StatusListEmpty_SL(SqListL)//判斷線性表是否為空
{
if(L.length==0)returnTRUE;
elsereturnFALSE;
}
StatusGetElem_SL(SqListL,inti,ElemType&e)//用e返回L中第i個數據元素的值(注意:下標由0開始的)
{
if(L.length==0/*||i<1*/||i>L.length)returnERROR;
e=*(L.elem+i);
returnOK;
}
StatusClearList_SL(SqList&L)//將線性表置為空表
{
L.length=0;
returnOK;
}
intLocateElem_SL(SqList&L,ElemTypee)//返回L中第1個與e滿足關系的數據元素的位序
{
inti;
if(L.length==0)return0;
for(i=0;i<L.length;i++)
{
if(e==*(L.elem+i))//找到
break;
}
if(i>=L.length)return0;//沒有找到
return(i+1);
}
StatusListDelete_SL(SqList&L,inti,ElemType&e)
{
//在順序線性表L中刪除第i個元素,並用e返回其值
//i的合法值為1<=i<=ListLength_SL(L)
ElemType*p,*q;
if((i<1)||(i>L.length))returnERROR;//i的值不合法
p=&(L.elem[i-1]);//p為被刪除元素的位置
e=*p;//被刪除元素的值賦給e
q=L.elem+L.length-1;//表尾元素的位置
for(++p/*++p是指被刪除元素的下一個元素開始左移*/;p<=q;++p)//被刪除元素之後的元素左移
*(p-1)=*p;
--L.length;//表長減1
returnOK;
}
StatusListTraverse(SqListL)//遍歷線性表元素
{
inti;
for(i=0;i<L.length;i++)
visit(*(L.elem+i));
cout<<endl;
returnOK;
}
StatusListInsert_SL(SqList&L,inti,ElemTypee)
{
//在L中第i個位置之前插入新的元素e,
//i的合法值為1<=i<=ListLength_SL(L)+1
ElemType*newbase,*q,*p;
if(i<1||i>L.length+1)returnERROR;//i值不合法
if(L.length>=L.listsize)
{//當前存儲空間已滿,增加分配
newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);//存儲分配失敗
L.elem=newbase;//新基址
L.listsize+=LIST_INCREMENT;//增加存儲容量
}
q=&(L.elem[i-1]);//q為插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;//插入e
++L.length;//表長增1
returnOK;
}
intListLength_SL(SqListL)//線性表長度
{
return(L.length);
}
intmain(void)
{
/***************************
Callthealgorithminhere.
****************************/
return1;
}
這個是最簡單的線性表,它沒有使用到類.都是過程化。
② 常見的排序演算法—選擇，冒泡，插入，快速，歸並
太久沒看代碼了，最近打算復習一下java，又突然想到了排序演算法，就把幾種常見的排序演算法用java敲了一遍，這里統一將無序的序列從小到大排列。
選擇排序是一種簡單直觀的排序演算法。它的工作原理是：第一次從待排序的數據元素中選出最小的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小元素，繼續放在下一個位置，直到待排序元素個數為0。
選擇排序代碼如下：
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("經過選擇排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
冒泡排序是一種比較基礎的排序演算法，其思想是相鄰的元素兩兩比較，較大的元素放後面，較小的元素放前面，這樣一次循環下來，最大元素就會歸位，若數組中元素個數為n，則經過（n-1）次後，所有元素就依次從小到大排好序了。整個過程如同氣泡冒起，因此被稱作冒泡排序。
選擇排序代碼如下：
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("經過冒泡排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
插入排序也是一種常見的排序演算法，插入排序的思想是：創建一個與待排序數組等大的數組，每次取出一個待排序數組中的元素，然後將其插入到新數組中合適的位置，使新數組中的元素保持從小到大的順序。
插入排序代碼如下：
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("經過插入排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
快速排序的效率比冒泡排序演算法有大幅提升。因為使用冒泡排序時，一次外循環只能歸位一個值，有n個元素最多就要執行（n-1）次外循環。而使用快速排序時，一次可以將所有元素按大小分成兩堆，也就是平均情況下需要logn輪就可以完成排序。
快速排序的思想是：每趟排序時選出一個基準值（這里以首元素為基準值），然後將所有元素與該基準值比較，並按大小分成左右兩堆，然後遞歸執行該過程，直到所有元素都完成排序。
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
歸並排序是建立在歸並操作上的一種有效的排序演算法，歸並排序對序列的元素進行逐層折半分組，然後從最小分組開始比較排序，每兩個小分組合並成一個大的分組，逐層進行，最終所有的元素都是有序的。
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
歸並排序這里我使用了left，right等變數，使其可以通用，並沒有直接用數字表示那麼明確，所以給出相關偽代碼，便於理解。
Mergesort(arr[0...n-1])
//輸入：一個可排序數組arr[0...n-1]
//輸出：非降序排列的數組arr[0...n-1]
if n>1
arr[0...n/2-1] to arr_1[0...(n+1)/2-1]//確保arr_1中元素個數>=arr_2中元素個數
//對於總個數為奇數時，arr_1比arr_2中元素多一個；對於總個數為偶數時，沒有影響
arr[n/2...n-1] to arr_2[0...n/2-1]
Mergesort(arr_1[0...(n+1)/2-1])
Mergesort(arr_2[0...n/2-1])
Merge(arr_1,arr_2,arr)
Merge(arr_1[0...p-1],arr_2[0...q-1],arr[0...p+q-1])
//輸入：兩個有序數組arr_1[0...p-1]和arr_2[0...q-1]
//輸出：將arr_1與arr_2兩數組合並到arr
int i<-0;j<-0;k<-0
while i
<p span="" do<="" jif arr_1[i] <= arr_2[j]
arr[k] <- arr_1[i]
i<-i+1
else arr[k] <- arr_2[j];j<-j+1
k<-k+1
if i=p
arr_2[j...q-1] to arr[k...p+q-1]
else arr_1[i...p-1] to arr[k...p+q-1]
package test_1;
import java.util.Scanner;
public class Test01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr_1 = new int[10];
for(int i = 0 ; i < 10 ; i++)
arr_1[i] = sc.nextInt();
Sort demo_1 = new Sort();
//1~5一次只能運行一個，若多個同時運行，則只有第一個有效，後面幾個是無效排序。因為第一個運行的已經將帶排序數組排好序。
demo_1.Select_sort(arr_1);//-----------------------1
//demo_1.Bubble_sort(arr_1);//---------------------2
/* //---------------------3
demo_1.Quick_sort(arr_1, 0 , arr_1.length - 1);
System.out.print("經過快速排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
//demo_1.Insert_sort(arr_1);//--------------------4
/* //--------------------5
demo_1.Mergesort(arr_1,0,arr_1.length - 1);
System.out.print("經過歸並排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
}
}
class Sort {
public void swap(int arr[],int a, int b) {
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("經過選擇排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("經過冒泡排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("經過插入排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
}
若有錯誤，麻煩指正，不勝感激。
③ 1.已知順序表L遞增有序，編寫一個演算法，將X插入到線性表的適當位置上，以保持線性表的有序性 用C語言
在處理已知遞增有序的順序表L時，我們需要設計一個高效的插入演算法，確保在插入新元素X後，線性表仍保持有序。這可以通過遍歷有序表，找到X應當插入的位置，並進行相應的調整來實現。
具體來說，可以採用二分查找法來定位X的正確位置，以減少不必要的比較次數。首先，初始化兩個指針low和high，分別指向順序表L的起始位置和結束位置。接著，進入循環，計算中間位置mid，比較X與L[mid]的大小關系。如果X小於等於L[mid]，則將high更新為mid，繼續在左半部分查找；反之，將low更新為mid+1，繼續在右半部分查找。當low大於high時，說明找到了X的正確插入位置。
在找到正確位置後，從後向前移動指針，依次將原有元素向後移動一位，為X騰出空間。具體地，從位置high開始，將L[high]賦值給L[high+1]，直到當前位置為low-1。最後，將X插入到low位置即可。
通過這種方法，我們可以在保持線性表有序的前提下，高效地插入新元素X。整個過程的時間復雜度為O(n)，其中n為線性表的長度。
值得注意的是，上述方法僅適用於已知線性表有序的情況。如果線性表原本無序，我們需要先進行排序處理，然後再進行插入操作。排序演算法的選擇會直接影響到插入操作的效率。
在C語言中，可以使用指針和數組來實現上述演算法。具體代碼如下：
c
void insertInOrder(int *L, int n, int X) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (X <= L[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (int i = n - 1; i >= low; i--) {
L[i + 1] = L[i];
}
L[low] = X;
}
以上代碼展示了如何在C語言中實現上述插入演算法，以保持線性表的有序性。