數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)
數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)一般常
用的有兩種 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
? 2.1 順序存儲(chǔ)結(jié)構(gòu)
發(fā)揮想象力啊。 舉個(gè)列子。數(shù)組妹萨。1-2-3-4-5-6-7-8-9-10。這個(gè)就是一個(gè)順序存儲(chǔ)結(jié)構(gòu) ，存儲(chǔ)是按順序的 舉 例說明啊套才。 棧。做開發(fā)的都熟悉慕淡。棧是先進(jìn)后出 背伴，后進(jìn)先出的形式 對(duì)不對(duì) ?!他的你可以這樣理解
hello world 在棧里面從棧底到棧頂?shù)倪壿嬕来螢?h-e-l-l-o-w-o-r-l-d 這就是順序存儲(chǔ) 再比如 隊(duì)列 ，隊(duì)列 是先進(jìn)先出的對(duì)吧峰髓，從頭到尾 h-e-l-l-o-w-o-r-l-d 就是這樣排對(duì)的
? 2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
再次發(fā)揮想象力 這個(gè)稍微復(fù)雜一點(diǎn) 這個(gè)圖片我一直弄好 傻寂，回頭找美工問問，再貼上 例如 還是一個(gè)數(shù)組
1-2-3-4-5-6-7-8-9-10 鏈?zhǔn)酱鎯?chǔ)就不一樣了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地 址)-6(地址)-10(地址)携兵。每個(gè)數(shù)字后面跟著一個(gè)地址 而且存儲(chǔ)形式不再是順序 疾掰，也就說順序亂了，1(地址) 1 后面跟著的這個(gè)地址指向的是 2眉孩，2 后面的地址指向的是 3个绍，3 后面的地址指向是誰你應(yīng)該清楚了吧。他 執(zhí)行的時(shí)候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)浪汪，但是存儲(chǔ) 的時(shí)候就是完全隨機(jī)的巴柿。明白了?!
單向鏈表\雙向鏈表\循環(huán)鏈表
還是舉例子。理解最重要死遭。不要去死記硬背 哪些什么广恢。定義啊。邏輯啊呀潭。理解才是最重要滴
3.1 單向鏈表
A->B->C->D->E->F->G->H. 這就是單向鏈表 H 是頭 A 是尾 像一個(gè)只有一個(gè)頭的火車一樣 只能一個(gè)頭拉
著跑
3.2 雙向鏈表
數(shù)組和鏈表區(qū)別:
數(shù)組:數(shù)組元素在內(nèi)存上連續(xù)存放钉迷，可以通過下標(biāo)查找元素;插入、刪除需要移動(dòng)大量元素钠署，比較適用元
素很少變化的情況
鏈表:鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的糠聪，查找慢，插入谐鼎、刪除只需要對(duì)元素指針重新賦值舰蟆，效率高
3.3 循環(huán)鏈表
循環(huán)鏈表是與單向鏈表一樣，是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，所不同的是身害，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指 向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)味悄，從而構(gòu)成一個(gè)環(huán)形的鏈。發(fā)揮想象力 A->B->C->D->E->F->G->H->A. 繞成一個(gè)圈塌鸯。就像蛇吃自己的這就是循環(huán) 不需要去死記硬背哪些理論知識(shí)侍瑟。
4.1 什么是二叉樹
樹形結(jié)構(gòu)下,兩個(gè)節(jié)點(diǎn)以內(nèi) 都稱之為二叉樹 不存在大于 2 的節(jié)點(diǎn) 分為左子樹 右子樹 有順序 不能顛 倒 ，懵逼了吧丙猬，你肯定會(huì)想這是什么玩意涨颜，什么左子樹右子樹 ，都什么跟什么鬼? 現(xiàn)在我以普通話再講 一遍淮悼，你把二叉樹看成一個(gè)人 咐低，人的頭呢就是樹的根 ，左子樹就是左手袜腥，右子樹就是右手见擦，左右手可以 都沒有(殘疾嘛呀邢，聲明一下曙蒸，絕非歧視殘疾朋友，勿怪列粪，勿怪就是舉個(gè)例子福侈，i am very sorry) , 左右 手呢可以有一個(gè)酒来，就是不能顛倒。這樣講應(yīng)該明白了吧
二叉樹有五種表現(xiàn)形式
1.空的樹(沒有節(jié)點(diǎn))可以理解為什么都沒 像空氣一樣
2.只有根節(jié)點(diǎn)肪凛。 (理解一個(gè)人只有一個(gè)頭 其他的什么都沒堰汉，說的有點(diǎn)恐怖) 3.只有左子樹 (一個(gè)頭 一個(gè)左手 感覺越來越寫不下去了)
4.只有右子樹
5.左右子樹都有
二叉樹可以轉(zhuǎn)換成森林 樹也可以轉(zhuǎn)換成二叉樹。這里就不介紹了 你做項(xiàng)目絕對(duì)用不到 數(shù)據(jù)結(jié)構(gòu)大致介紹這么多吧伟墙。理解為主, 別死記翘鸭，死記沒什么用
1、不用中間變量,用兩種方法交換 A 和 B 的值
2戳葵、求最大公約數(shù)
3就乓、模擬棧操作
? 棧是一種數(shù)據(jù)結(jié)構(gòu)，特點(diǎn):先進(jìn)后出 -
? 練習(xí):使用全局變量模擬棧的操作
include <stdio.h> #include <stdbool.h> #include <assert.h>
//保護(hù)全局變量:在全局變量前加 static 后拱烁，這個(gè)全局變量就只能在本文件中使用 static int data[1024];//棧最多能保存 1024 個(gè)數(shù)據(jù)
static int count = 0;//目前已經(jīng)放了多少個(gè)數(shù)(相當(dāng)于棧頂位置)
4生蚁、排序算法
選擇排序、冒泡排序戏自、插入排序三種排序算法可以總結(jié)為如下:
都將數(shù)組分為已排序部分和未排序部分邦投。
1.選擇排序?qū)⒁雅判虿糠侄x在左端，然后選擇未排序部分的最小元素和未排序部分的第一個(gè)元素交換擅笔。 2.冒泡排序?qū)⒁雅判虿糠侄x在右端尼摹，在遍歷未排序部分的過程執(zhí)行交換见芹，將最大元素交換到最右端。 3.插入排序?qū)⒁雅判虿糠侄x在左端蠢涝，將未排序部分元的第一個(gè)元素插入到已排序部分合適的位置。 4.1阅懦、選擇排序
? 【選擇排序】:最值出現(xiàn)在起始端
? 第1趟:在n個(gè)數(shù)中找到最小(大)數(shù)與第一個(gè)數(shù)交換位置
? 第2趟:在剩下n-1個(gè)數(shù)中找到最小(大)數(shù)與第二個(gè)數(shù)交換位置 ? 重復(fù)這樣的操作...依次與第三個(gè)和二、第四個(gè)...數(shù)交換位置
? 第n-1趟，最終可實(shí)現(xiàn)數(shù)據(jù)的升序(降序)排列耳胎。
/**
選擇排序
*/
void xuanzePaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
for (int i = 0; i < arr.count - 1; i++) {
for (int j = i + 1; j < arr.count; j++) {
if ([arr[i] intValue] > [arr[j] intValue]) {
int temp = [arr[j] intValue];
arr[j] = arr[i];
arr[i] = [NSString stringWithFormat:@"%d",temp];
}
}
}
NSLog(@"%@",arr);
}
4.2惯吕、冒泡排序
? 【冒泡排序】:相鄰元素兩兩比較，比較完一趟怕午，最值出現(xiàn)在末尾
? 第1趟:依次比較相鄰的兩個(gè)數(shù)废登，不斷交換(小數(shù)放前，大數(shù)放后)逐個(gè)推進(jìn)郁惜，最值最后出現(xiàn)在第n
個(gè)元素位置
? 第2趟:依次比較相鄰的兩個(gè)數(shù)堡距，不斷交換(小數(shù)放前，大數(shù)放后)逐個(gè)推進(jìn)兆蕉，最值最后出現(xiàn)在第n-1
個(gè)元素位置
? ............
? 第n-1趟:依次比較相鄰的兩個(gè)數(shù)羽戒，不斷交換(小數(shù)放前，大數(shù)放后)逐個(gè)推進(jìn)虎韵，最值最后出現(xiàn)在第
2 個(gè)元素位置
/**
冒泡排序
*/
void maoPaoPaixu(void) {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
for (int i = 0; i < arr.count; i++) {
for (int j = 0; j < arr.count - 1 - i; j++) {
if ([arr[j] intValue] > [arr[j+1] intValue]) {
int temp = [arr[j] intValue];
arr[j] = arr[j + 1];
arr[j+ 1] = [NSString stringWithFormat:@"%d",temp];
}
}
}
NSLog(@"%@",arr);
}
5易稠、折半查找(二分查找)
折半查找:優(yōu)化查找時(shí)間(不用遍歷全部數(shù)據(jù))
折半查找的原理:
? 1> 數(shù)組必須是有序的
? 2> 必須已知 min 和 max(知道范圍)
? 3> 動(dòng)態(tài)計(jì)算 mid 的值，取出 mid 對(duì)應(yīng)的值進(jìn)行比較
? 4> 如果 mid 對(duì)應(yīng)的值大于要查找的值包蓝，那么 max 要變小為 mid-1
? 5> 如果 mid 對(duì)應(yīng)的值小于要查找的值驶社，那么 min 要變大為 mid+1
// 已知一個(gè)有序數(shù)組, 和一個(gè) key, 要求從數(shù)組中找到 key 對(duì)應(yīng)的索引位置
/**
二分查找
@param ary
@param findNum
@return
*/
NSInteger efChazhao(NSArray *ary,NSInteger findNum) {
NSInteger mid = (ary.count - 1) / 2.0;
if (mid == 0) {
return -1; //找不到
}
if (findNum == [ary[mid] integerValue]) {
return mid;//返回所在的序列號(hào)
}
else if(findNum > [ary[mid] integerValue]) {
return efChazhao([ary subarrayWithRange:NSMakeRange(mid + 1, ary.count - mid - 1)], findNum);
}
else {
return efChazhao([ary subarrayWithRange:NSMakeRange(0, mid + 1)], findNum);
}
}
void erfenChazhao() {
//二分查找一定是有序的數(shù)組
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
NSInteger mid = efChazhao(arr,15);
NSLog(@"%ld",(long)mid);
}
/**
快速排序
*/
void ksPaixu(NSMutableArray *arr,NSInteger left,NSInteger right) {
if(left == right) return;
NSInteger i = left;
NSInteger j = right;
NSInteger key = [arr[left] integerValue];
while (i < j) {
while (i < j && key <= [arr[j] integerValue]) {
j--;
}
arr[i] = arr[j];
while (i<j && key >= [arr[i] integerValue]) {
I++;
}
arr[j] = arr[i];
}
arr[i] = [NSString stringWithFormat:@"%ld",(long)key];
ksPaixu(arr, left, i-1);
ksPaixu(arr, i+1, right);
}
void kuaisuPaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
ksPaixu(arr, 0, arr.count-1);
NSLog(@"%@",arr);
}
/**
插入排序
*/
void charuPaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
for (int i = 1; i<arr.count; i++) {
int j = I;
NSInteger temp = [arr[i] integerValue];
while (j > 0 && temp < [arr[j-1] integerValue]) {
[arr replaceObjectAtIndex:j withObject:arr[j-1]];
j--;
}
[arr replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%ld",(long)temp]];
}
NSLog(@"%@",arr);
}
/**
希爾排序
*/
void xierPaixu() {
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
int gap = arr.count / 2.0;
while (gap >= 1) {
for (int i = gap; i < arr.count; i++) {
NSInteger temp = [arr[i] integerValue];
int j = I;
while (j >= gap && temp < [arr[j- gap] integerValue]) {
[arr replaceObjectAtIndex:j withObject:arr[j-gap]];
j-=gap;
}
[arr replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%ld",(long)temp]];
}
gap = gap / 2.0;
}
NSLog(@"%@",arr);
}
字符串反正
給定字符串 "hello,world",實(shí)現(xiàn)將其反轉(zhuǎn)。輸出結(jié)果:dlrow,olleh
- (NSString *)reversalString:(NSString *)originString{
NSString *resultStr = @"";
for (NSInteger i = originString.length -1; i >= 0; i--) {
NSString *indexStr = [originString substringWithRange:NSMakeRange(i, 1)];
resultStr = [resultStr stringByAppendingString:indexStr];
}
return resultStr;
}
void char_reverse(char *cha){
char *begin = cha;
char *end = cha + strlen(cha) - 1;
while (begin <= end) {
char temp = *end;
*(end--) = *begin;
*(begin++) = temp;
}
}
// 調(diào)用
char cha[] = "hello,world";
char_reverse(cha);
printf("%s",cha);
結(jié)果：dlrow,olleh
序數(shù)組合并
將有序數(shù)組 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并為 {1,2,3,4,5,6,6,7,8,9,9,10,11,12}
// 將有序數(shù)組a和b的值合并到一個(gè)數(shù)組result當(dāng)中测萎，且仍然保持有序
void mergeList(int a[], int aLen, int b[], int bLen, int result[]);
void mergeList(int a[], int aLen, int b[], int bLen, int result[])
{
int p = 0; // 遍歷數(shù)組a的指針
int q = 0; // 遍歷數(shù)組b的指針
int i = 0; // 記錄當(dāng)前存儲(chǔ)位置
// 任一數(shù)組沒有到達(dá)邊界則進(jìn)行遍歷
while (p < aLen && q < bLen) {
// 如果a數(shù)組對(duì)應(yīng)位置的值小于b數(shù)組對(duì)應(yīng)位置的值
if (a[p] <= b[q]) {
// 存儲(chǔ)a數(shù)組的值
result[i] = a[p];
// 移動(dòng)a數(shù)組的遍歷指針
p++;
}
else{
// 存儲(chǔ)b數(shù)組的值
result[i] = b[q];
// 移動(dòng)b數(shù)組的遍歷指針
q++;
}
// 指向合并結(jié)果的下一個(gè)存儲(chǔ)位置
i++;
}
// 如果a數(shù)組有剩余
while (p < aLen) {
// 將a數(shù)組剩余部分拼接到合并結(jié)果的后面
result[i] = a[p++];
i++;
}
// 如果b數(shù)組有剩余
while (q < bLen) {
// 將b數(shù)組剩余部分拼接到合并結(jié)果的后面
result[i] = b[q++];
i++;
}
}
HASH 算法
? 哈希表
例:給定值是字母 a亡电，對(duì)應(yīng) ASCII 碼值是 97，數(shù)組索引下標(biāo)為 97绳泉。
這里的 ASCII 碼逊抡，就算是一種哈希函數(shù)，存儲(chǔ)和查找都通過該函數(shù)零酪，有效地提高查找效率冒嫡。
? 在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入"abaccdeff"四苇，輸出'b'字符(char)是一個(gè)長度為8 的數(shù)據(jù)類型孝凌，因此總共有 256 種可能。每個(gè)字母根據(jù)其 ASCII 碼值作為數(shù)組下標(biāo)對(duì)應(yīng)數(shù)組種的一個(gè)數(shù) 字月腋。數(shù)組中存儲(chǔ)的是每個(gè)字符出現(xiàn)的次數(shù)蟀架。
查找兩個(gè)子視圖的共同父視圖 思路:分別記錄兩個(gè)子視圖的所有父視圖并保存到數(shù)組中瓣赂，然后倒序?qū)ふ?直至找到第一個(gè)不一樣的父視圖。
// 查找兩個(gè)視圖的共同父視圖
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)view other:(UIView *)viewOther;
- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther
{
NSMutableArray *result = [NSMutableArray array];
// 查找第一個(gè)視圖的所有父視圖
NSArray *arrayOne = [self findSuperViews:viewOne];
// 查找第二個(gè)視圖的所有父視圖
NSArray *arrayOther = [self findSuperViews:viewOther];
int i = 0;
// 越界限制條件
while (i < MIN((int)arrayOne.count, (int)arrayOther.count)) {
// 倒序方式獲取各個(gè)視圖的父視圖
UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - 1];
UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1];
// 比較如果相等 則為共同父視圖
if (superOne == superOther) {
[result addObject:superOne];
i++;
}
// 如果不相等片拍，則結(jié)束遍歷
else{
break;
}
}
return result;
}
- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
// 初始化為第一父視圖
UIView *temp = view.superview;
// 保存結(jié)果的數(shù)組
NSMutableArray *result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
// 順著superview指針一直向上查找
temp = temp.superview;
}
return result;
}
- (void)viewDidLoad {
[super viewDidLoad];
Class commonClass1 = [self commonClass1:[ViewA class] andClass:[ViewC
class]];
NSLog(@"%@",commonClass1);
// 2018-03-22 17:36:01.868966+0800[84288:2458900] ViewD
}
//獲取所有父類
- (NSArray *)superClasses:(Class)class {
if (class == nil) {
return @[];
}
NSMutableArray *result = [NSMutableArray array];
while (class != nil) {
[result addObject:class];
class = [class superclass];
}
return [result copy];
}
- (Class)commonClass1:(Class)classA andClass:(Class)classB {
NSArray *arr1 = [self superClasses:classA];
NSArray *arr2 = [self superClasses:classB];
for (NSUInteger i = 0; i < arr1.count; ++i) {
Class targetClass = arr1[i];
for (NSUInteger j = 0; j < arr2.count; ++j) {
if (targetClass == arr2[j]) {
return targetClass;
} }
}
return nil;
}
- (Class)commonClass2:(Class)classA andClass:(Class)classB{
NSArray *arr1 = [self superClasses:classA];
NSArray *arr2 = [self superClasses:classB];
NSSet *set = [NSSet setWithArray:arr2];
for (NSUInteger i =0; i<arr1.count; ++i) {
Class targetClass = arr1[i];
if ([set containsObject:targetClass]) {
return targetClass;
}
}
return nil;
}
/**
求無序數(shù)組當(dāng)中的中位數(shù)(快排思想煌集，選中關(guān)鍵字，高低交替掃描)
示例:
[@"1",@"9",@"6",@"8",@"3",@"2"]
輸出:
@"3"
*/
+ (void)findMedianValue {undefined
NSMutableArray *array = [NSMutableArray arrayWithObjects:@"1",@"9",@"6",@"8",@"3",@"2", nil];
NSLog(@"輸入數(shù)據(jù):%@",array);
NSInteger low = 0;
NSInteger high = array.count - 1;
NSInteger mid = high/2;
NSInteger result = [self arraySort:array IndexStart:low IndexEnd:high];
while(result != mid) {undefined
if (result < mid) {undefined
result = [self arraySort:array IndexStart:result+1 IndexEnd:high];
}else {undefined
result = [self arraySort:array IndexStart:low IndexEnd:result-1];
}
}
NSLog(@"中位數(shù)是:%@",array[mid]);
}
+ (NSInteger)arraySort:(NSMutableArray *)array IndexStart:(NSInteger)indexStart IndexEnd:(NSInteger)indexEnd {undefined
NSInteger keyValue = [array[indexEnd] integerValue];
NSInteger lastEnd = indexEnd;
while (indexStart < indexEnd) {undefined
while (indexStart < indexEnd && [array[indexStart] integerValue] <= keyValue) {undefined
indexStart++;
}
while (indexStart < indexEnd && [array[indexEnd] integerValue] >= keyValue) {undefined
indexEnd--;
}
if (indexStart < indexEnd) {undefined
NSString *temp = array[indexStart];
array[indexStart] = array[indexEnd];
array[indexEnd] = temp;
}
}
NSString *temp = array[indexEnd];
array[indexEnd] = array[lastEnd];
array[lastEnd] = temp;
return indexStart;
}
//給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值捌省，找出數(shù)組中和為目標(biāo)值得的倆個(gè)數(shù)
//給定nums = [2,7,11,15] ,target = 9 -------返回【0苫纤，1】
● 第一層for循環(huán)從索引0到倒數(shù)第二個(gè)索引拿到每個(gè)數(shù)組的元素
●第二個(gè)for循環(huán)遍歷上一層for循環(huán)拿到的元素的后面得所有元素
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int[] result = new int[2];
for(int i = 0; i < len; i++){
for(int j = i+1; j < len; j++){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j;
return result;
} }
}
return result;
}
}
//查找第一個(gè)只出現(xiàn)一次的字符（hash查找）
# define SIZE 256
char GetChar(char str[])
{
if(!str)
return 0;
char* p = NULL;
unsigned count[SIZE] = {0};
char buffer[SIZE];
char* q = buffer;
for(p=str; *p!=0; p++)
{
if(++count[(unsigned char)*p] == 1)
*q++ = *p;
}
for (p=buffer; p<q; p++)
{
if(count[(unsigned char)*p] == 1)
return *p;
}
return 0;
}
char findFirstChar(char* cha)
{
char result = '\0';
// 定義一個(gè)數(shù)組 用來存儲(chǔ)各個(gè)字母出現(xiàn)次數(shù)
int array[256];
// 對(duì)數(shù)組進(jìn)行初始化操作
for (int i=0; i<256; i++) {
array[i] =0;
}
// 定義一個(gè)指針 指向當(dāng)前字符串頭部
char* p = cha;
// 遍歷每個(gè)字符
while (*p != '\0') {
// 在字母對(duì)應(yīng)存儲(chǔ)位置 進(jìn)行出現(xiàn)次數(shù)+1操作
array[*(p++)]++;
}
// 將P指針重新指向字符串頭部
p = cha;
// 遍歷每個(gè)字母的出現(xiàn)次數(shù)
while (*p != '\0') {
// 遇到第一個(gè)出現(xiàn)次數(shù)為1的字符，打印結(jié)果
if (array[*p] == 1)
{
result = *p;
break;
}
// 反之繼續(xù)向后遍歷
p++;
}
return result;
}
// 無序數(shù)組查找中位數(shù)
int list[10] = {12,3,10,8,6,7,11,13,9};
// 3 6 7 8 9 10 11 12 13
// ^
int median = findMedian(list, 10);
printf("the median is %d \n", median);
//求一個(gè)無序數(shù)組的中位數(shù)
int findMedian(int a[], int aLen)
{
int low = 0;
int high = aLen - 1;
int mid = (aLen - 1) / 2;
int div = PartSort(a, low, high);
while (div != mid)
{
if (mid < div)
{
//左半?yún)^(qū)間找
div = PartSort(a, low, div - 1);
}
else
{
//右半?yún)^(qū)間找
div = PartSort(a, div + 1, high);
}
}
//找到了
return a[mid];
}
int PartSort(int a[], int start, int end)
{
int low = start;
int high = end;
//選取關(guān)鍵字
int key = a[end];
while (low < high)
{
//左邊找比key大的值
while (low < high && a[low] <= key)
{
++low;
}
//右邊找比key小的值
while (low < high && a[high] >= key)
{
--high;
}
if (low < high)
{
//找到之后交換左右的值
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}
int temp = a[high];
a[high] = a[end];
a[end] = temp;
return low;
}
定義一個(gè)鏈表
// 定義一個(gè)鏈表
struct Node {
int data;
struct Node *next;
};
@interface ReverseList : NSObject
// 鏈表反轉(zhuǎn)
struct Node* reverseList(struct Node *head);
// 構(gòu)造一個(gè)鏈表
struct Node* constructList(void);
// 打印鏈表中的數(shù)據(jù)
void printList(struct Node *head);
@end
#import "ReverseList.h"
@implementation ReverseList
struct Node* reverseList(struct Node *head)
{
// 定義遍歷指針纲缓，初始化為頭結(jié)點(diǎn)
struct Node *p = head;
// 反轉(zhuǎn)后的鏈表頭部
struct Node *newH = NULL;
// 遍歷鏈表
while (p != NULL) {
// 記錄下一個(gè)結(jié)點(diǎn)
struct Node *temp = p->next;
// 當(dāng)前結(jié)點(diǎn)的next指向新鏈表頭部
p->next = newH;
// 更改新鏈表頭部為當(dāng)前結(jié)點(diǎn)
newH = p;
// 移動(dòng)p指針
p = temp;
}
// 返回反轉(zhuǎn)后的鏈表頭結(jié)點(diǎn)
return newH;
}
struct Node* constructList(void)
{
// 頭結(jié)點(diǎn)定義
struct Node *head = NULL;
// 記錄當(dāng)前尾結(jié)點(diǎn)
struct Node *cur = NULL;
for (int i = 1; i < 5; i++) {
struct Node *node = malloc(sizeof(struct Node));
node->data = i;
// 頭結(jié)點(diǎn)為空卷拘，新結(jié)點(diǎn)即為頭結(jié)點(diǎn)
if (head == NULL) {
head = node;
}
// 當(dāng)前結(jié)點(diǎn)的next為新結(jié)點(diǎn)
else{
cur->next = node;
}
// 設(shè)置當(dāng)前結(jié)點(diǎn)為新結(jié)點(diǎn)
cur = node;
}
return head;
}
void printList(struct Node *head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("node is %d \n", temp->data);
temp = temp->next;
}
}
@end
